[Heap, 난이도 중하] 프로그래머즈, 더 맵게

scoville의 길이 제한이 1,000,000인 것을 보아 힙을 쓰지 않으면 통과할 수 없는 문제라는 것을 알 수 있다.

이 문제 역시 힙의 원리로 돌아가는 priority_queue 라이브러리로 해결하면 쉽게 풀 수 있다.

삽입, 삭제 모두 시간 복잡도가 O(logn)이기 때문에 최고의 시간 복잡도로 해결할 수 있는 것이다.

 

오름차순으로 정렬하여, pop할 때 가장 작은 원소가 나오게 하였고

이렇게 덜 매운 순위 1,2위를 뽑아서 주어진 공식에 맞게 새로운 스코빌 지수를 계산하여 pq에 push해주는 과정을 반복했다.

pq의 top은 최소 스코빌지수를 나타내므로 pq.top()이 K이상일 경우 반복문을 종료하고, pq.top()이 K미만인데 pq에 원소가 1개 이하라면 더 이상 섞을 수 있는 상태가 아니므로 -1을 그대로 리턴해주었다.

 

정확성, 효율성 모두 만점

 

#include <vector>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > pq;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int first,second,new_food;
    for(int i=0;i<scoville.size();i++) pq.push(scoville[i]);
    if(pq.top()>=K) return 0;
    while(1){
        first=pq.top();
        pq.pop();
        second=pq.top();
        pq.pop();
        new_food=first+(2*second);
        pq.push(new_food);
        answer++;
        if(pq.top()>=K) break;
        if(pq.size()<2) return -1;
    }
    return answer;
}