[Algorithm] 프로그래머스 더 맵게 - C++, 우선순위 큐

코딩테스트 연습 - 더 맵게

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int count = 0;

    // make input
    priority_queue<int> q;
    for(int i = 0; i < scoville.size(); i++)
        q.push(-scoville[i]);
    
    while(q.size() >= 2){
        int first = -q.top();   q.pop();

        if(first >= K)
            return count;

        int second = -q.top();  q.pop();
        int newScov = first + (second * 2);
        count++; 

        q.push(-newScov);
    }
    
    if(-q.top() >= K)
        return count;
    return -1;
}

// 16m - 95.2
// 17m 30s

---

 일단 어디서 비슷한 문제를 본 거 같은데 잘 기억이 안나고... 단순히 우선순위 큐에 넣은 뒤 이를 비교해주면 되는 문제였습니다.

 

 처음에 문제 풀이를 할 때 '모든 음식' 이라는 키워드를 생각을 잘못해버려서 계속 틀렸었는데 K 와의 비교문은 q.top()을 처음 볼 때 해주시면 됩니다.

 그 외 테스트 16번인가 마지막이 틀렸다면 힙 사이즈가 1일때 마지막 비교를 해주시면 됩니다. 그걸 안하면 틀리게 나오는것 같아요.