[프로그래머스 42626] 더 맵게

• 출처: 프로그래머스 42626
• 분류: 힙 · Lv.2

문제

스코빌 지수 배열 scoville과 기준값 K가 주어진다. 가장 안 매운 음식 두 개를 가장 안 매운 것 + 두 번째로 안 매운 것 × 2로 섞어서 모든 음식의 스코빌 지수를 K 이상으로 만들어야 한다. 최소 섞는 횟수를 반환하고, 불가능하면 -1을 반환한다.

핵심

매번 “가장 작은 두 값”이 필요하므로 최소 힙을 쓴다. pop 두 번 → 섞어서 push → top이 K 이상이면 종료.

풀이

#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    int count = 0;

    while (pq.size() >= 2 && pq.top() < K) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        pq.push(a + b * 2);
        count++;
    }

    return pq.top() >= K ? count : -1;
}

메모

• priority_queue의 템플릿 파라미터는 <자료형, 컨테이너, 비교자> 순이다. 비교자만 바꾸고 싶어도 컨테이너를 반드시 명시해야 한다
• 기본 priority_queue<int>는 less<int> 비교 → 최대 힙. greater<int>로 바꾸면 최소 힙
• 주요 API: push()/pop()은 O(log N), top()은 O(1), size()/empty()는 O(1)
• 범위 생성자 pq(begin, end)는 내부적으로 make_heap을 호출해서 O(N). 반복문으로 push를 N번 하면 O(N log N)이므로 범위 생성자가 유리하다
• 종료 조건이 두 가지다: pq.top() >= K(성공) 또는 pq.size() < 2인데 아직 top < K(실패)
• 섞은 결과는 항상 두 원소보다 크므로 힙 크기가 매 반복 1씩 줄어든다. 무한 루프 없음

복잡도

풀이	시간	공간
최소 힙	O(N log N)	O(N)