서리 개인 개발 블로그

풀이 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

#define FAIL -1

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(auto it : scoville)
    {
        pq.push(it);
    }

    while(pq.size() > 1 && pq.top() < K)
    {
        int less_1 = pq.top();
        pq.pop();
        int less_2 = pq.top();
        pq.pop();

        int mixScoville = less_1 + less_2 * 2;
        answer++;

        pq.push(mixScoville);
    }

    if(pq.top() < K)
    {
        answer = FAIL;
    }

    return answer;
}

기타

- 코드 작성은 쉬웠는데, 제발 테스트 케이스가 조금 많았으면 좋겠다 ㅠㅠ.. (1개는 너무한거 아닌가)

- C#에서는 우선순위 큐를 직접 구현해서 사용했었는데, C++에서는 그냥 제공되서 작성에 편했다.

- 다른 사람 풀이를 보니 아래와 같이 작성해서 for문 돌려서 값을 넣을 필요 없이 바로 값을 넣을 수 있었다.

priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

풀이 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    //first : 트럭 무게
    //second : 다리 진입 시간
    queue<pair<int, int>> bridgeQueue;
    int sec = 1;
    int totWeight = 0;

    for(int i = 0; i < truck_weights.size(); i++, sec++)
    {
        if(bridgeQueue.size() != 0)
        {
            //경과시간이 선두 트럭 통과 시간보다 크면 이미 통과한 트럭이므로 디큐
            if(sec >= bridgeQueue.front().second + bridge_length)
            {
                totWeight -= bridgeQueue.front().first;
                bridgeQueue.pop();
            }
			
            //트럭 무게가 다리 하중을 넘으면 선두 트럭을 디큐하고 선두 트럭 기준으로 시간을 다시 계산한다.
            while(weight < truck_weights[i] + totWeight)
            {
                sec = bridgeQueue.front().second + bridge_length;
                totWeight -= bridgeQueue.front().first;
                bridgeQueue.pop();
            }
        }

        bridgeQueue.push(make_pair(truck_weights[i], sec));
        totWeight += truck_weights[i];
    }

    return bridgeQueue.back().second + bridge_length;
}

기타

- 이번 문제는 지문이 너무 불친절해서 지문 이해하는데 오래걸렸다. (지문이 이해가 안간다는 말들이 보이는거 보면 내가 한글을 못하는건 아닌거같다..)

풀이코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int GetAnswer(const vector<int>&, int);

int solution(vector<int> priorities, int location) {
    int answer = GetAnswer(priorities, location);
    return answer;
}

int GetAnswer(const vector<int>& priorities, int location)
{
    int result = 0;
    queue<pair<int, int>> iQueue;
    priority_queue<int> pQueue;
    for(int i = 0; i < priorities.size(); i++)
    {
        iQueue.push(make_pair(i, priorities[i]));
        pQueue.push(priorities[i]);
    }

    while(!iQueue.empty())
    {
        if(iQueue.front().second == pQueue.top())
        {
            pQueue.pop();
            result++;

            if(iQueue.front().first == location)
            {
                break;
            }
        }
        else
        {
            iQueue.push(iQueue.front());
        }
        iQueue.pop();
    }

    return result;
}

• vector의 값을 queue<pair<int, int>와 priority_queue<int>에 넣어준다.
• 그 뒤, 큐의 priority값과 우선순위 큐의 값을 비교해서 같으면 result를 증가시키고 다르면 큐의 첫번째 값을 맨 뒤로 옮겨준다.
• priority 값이 같을 때, location값을 비교하는데 location 값이 같으면 내가 요청한 문서를 찾은것이니 반복문을 나와 result 값을 반환한다.

기타

- 인수로 들어오는 vector 값으로 해결해보려고 했는데, 기본 케이스는 통과가 되나 제출 시의 테스트 케이스에서 불합격이 나는바람에 포기했다. (어떤 케이스에서 안되는지 알고싶은데 그걸 모르니 답답함...)

풀이 코드

#include <string>
#include <vector>

using namespace std;

#define COMPLETE 100

vector<int> GetAnswer(const vector<int>&, const vector<int>&);

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer = GetAnswer(progresses, speeds);
    return answer;
}

vector<int> GetAnswer(const vector<int>& progresses, const vector<int>& speeds)
{
    vector<int> result;
    for(int i = 0; i < progresses.size();)
    {
        int date = (COMPLETE - 1 - progresses[i]) / speeds[i] + 1;
        int releaseCount = 0;
        for(int j = i; j < progresses.size(); j++)
        {
            if(progresses[j] + speeds[j] * date >= COMPLETE)
            {
                releaseCount++;
            }
            else
            {
                break;
            }
        }

        result.push_back(releaseCount);
        i += releaseCount;
    }

    return result;
}

• 카테고리가 스택/큐로 분류되어있어서 큐를 사용할까 했는데, 이걸 굳이 큐까지 사용해야하나 싶어서 결국 결과 값을 카운팅해서 구했다.

기타

- 다른사람 풀이를 보니 반복문 하나만 사용해서 풀은 코드를 보게되었다.

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

- 처음에 이런식으로 작성하려고 생각했다가, answer에 값이 없을 때와 이미 들어간 값을 증감시키는 부분에 막혀서 카운팅을 따로 했었는데 vector.back()에 증감연산자 사용하는 방법이 있었다.

풀이 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define MAX 2

vector<pair<string, int>> GetSortedGenres(const vector<string>&, const vector<int>&);
unordered_map<string, vector<pair<int, int>>> GetSortedPlays
(const vector<pair<string, int>>&, const vector<string>&, const vector<int>&);

vector<int> solution(vector<string> genres, vector<int> plays) {
	
    //재생 수를 기준으로 내림차순으로 정렬 된 장르의 벡터를 가져온다.
    vector<pair<string, int>> genresVec = GetSortedGenres(genres, plays);
    //재생 수를 기준으로 내림차순으로 정렬 된 장르별 곡의 맵을 가져온다.
    unordered_map<string, vector<pair<int, int>>> playsMap = GetSortedPlays(genresVec, genres, plays);

    vector<int> answer;
    for(int i = 0; i < genresVec.size(); i++)
    {
        for(int j = 0; j < playsMap[genresVec[i].first].size() && j < MAX; j++)
        {
            //반환할 결과 값(벡터)에 장르별 곡의 길이(혹은 최대 2곡)까지 넣어준다.
            answer.push_back(playsMap[genresVec[i].first][j].first);
        }
    }

    return answer;
}

vector<pair<string, int>> GetSortedGenres(const vector<string>& genres, const vector<int>& plays)
{
    unordered_map<string, int> genresMap;
    for(int i = 0; i < genres.size() && i < plays.size(); i++)
    {
        genresMap[genres[i]] += plays[i];
    }

    //값(value)를 기준으로 내림차순 정렬을 해주기위해 map을 vector로 바꿔준다.
    vector<pair<string, int>> pVector;
    for(auto& it : genresMap)
    {
        pVector.push_back(it);
    }
	
    //내림차순 정렬(람다 사용)
    sort(pVector.begin(), pVector.end(), [](auto& p1, auto& p2)
    {
        return p1.second > p2.second;
    });

    return pVector;
}

unordered_map<string, vector<pair<int, int>>> GetSortedPlays
(const vector<pair<string, int>>& pairVec, const vector<string>& genres, const vector<int>& plays)
{
    unordered_map<string, vector<pair<int, int>>> map;
    for(int i = 0; i < genres.size() && i < plays.size(); i++)
    {
        map[genres[i]].push_back(make_pair(i, plays[i]));
    }

    for (auto& it : map)
    {
    	//map의 장르(Key)에 해당하는 곡(value(pair))들을 내림차순으로 정렬(람다 사용)
        sort(it.second.begin(), it.second.end(), [](auto& v1, auto& v2)
        {
            //곡의 플레이수가 같으면 고유번호를 기준으로 오름차순 정렬한다.
            if (v1.second == v2.second)
            {
                return v1.first < v2.first;
            }

            return v1.second > v2.second;
        });
    }

    return map;
}

• 각 곡 장르와 장르별 곡을 정렬해 반환하는 함수를 나눠 작성했지만, 반환 함으로써 값 복사가 일어나므로 solution에 다 작성하거나, 힙에 할당했으면 좀 더 좋았을 것 같다.

기타

- Lv3은 처음 풀어봤는데, Lv1, Lv2와 다르게 코드가 너무 길어져서 잘못하고 있는줄 알았다.

- C#이랑 람다 식을 작성하는 방법이 달랐다.

- 해당 문제를 풀면서 필요한 자료형을 찾다가 pair라는것을 알게 됨.