프로그래머스/더 맵게(힙 heap)/C++

문제 설명

 

힙을 사용하여 문제를 해결하는 능력만 있다면 풀 수 있는 문제.

 

 

주의할 점

: 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우를 처리해야 한다는 것. 모두 섞어서 하나의 스코빌 지수로 합하였는데도 K 이상이 되지 않는 경우를 처리해주어야 함.

 

 

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> pq;
    int answer = 0;

    for(int i = 0; i<scoville.size(); i++){ // 힙 초기화.
        pq.push(scoville[i]);
    }

    while(!pq.empty()){
        int least = pq.top();
        pq.pop();

        if(least >= K) break; // 조건 충족. 성공.
        if(pq.empty()) { // 힙이 빈 경우. 섞어서 새로운 스코빌 지수 만들 수 없음. 실패.
            answer = -1;
            break;
        }

        int second = pq.top();
        pq.pop();

        int newScoville = least + second * 2;
        pq.push(newScoville);
        answer++;
    }

    return answer;
}

 

 

 

피드백

: 우선순위 큐 초기화할 때 벡터 원소들로 할 수 있다. vector 컨테이너를 기반으로 하는 것이어서 혹시나 assign을 쓸 수 있나하고 거기까지는 시도해보았는데, 생성할 때 초기화하는 것은 시도해볼 생각을 못 해서 아쉽다.

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

힙에서 원소를 하나 꺼내고 힙이 비었는지 다시 체크하기보다는, 애초에 힙에 원소가 하나뿐인데 그 값이 K 이상이 아니라면 실패를 반환하도록 짜는 것이 더 나았을 듯 하다. 중복을 줄이자! 조금 더 깔끔하게 코드를 짜려고 노력해야 할 필요가 있다.