[ 프로그래머스 / 힙 ] 더 맵게 풀이

1. 문제

---

 

코딩테스트 연습 - 더 맵게

 

 

2. 소스코드

---

- 가장 안 매운 음식 2개를 섞어서 맵게 만든 뒤, 매운 정도가 K를 넘을 때의 최소횟수를 반환. 불가능 하면 -1

- 매번 정렬을 해서 답을 구할 수 도 있지만, 그러면 시간복잡도 때문에 PASS할 수 없다.

- 따라서, 힙을 사용해야한다.

- 대표적으로 우선순위 큐가 있다.

- 우선 순위큐에 비교함수를 바꿔 낮은 수가 가장 앞으로 오게 할 수 있지만, 그냥 -1을 곱해서 사용해도 된다.

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int len = scoville.size();
    
    priority_queue<int> pq;
    
    for(int i = 0 ; i < len; ++i){
        pq.push(-scoville[i]);
    }

    int time = 0;
    while(true){
        int cur = -pq.top(); pq.pop();
        if(cur < K){
            if(!pq.empty()){
                int next = -pq.top(); pq.pop();
                pq.push(-(cur + next * 2));
                time++;
            }
            else return -1;
        }
        else return time;
    }
}