99클럽 코테 스터디 25일차 TIL + 힙(C++)

문제

[프로그래머스] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

코드

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

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

    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto s : scoville)
        pq.push(s);

    while (pq.size() > 1) { // 최소 2개 이상 있어야 섞을 수 있음
        int first = pq.top();
        pq.pop();

        if (first >= K)
            return answer; // 모든 값이 K 이상일 경우

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

        int mix = first + second * 2;
        pq.push(mix);
        answer++;
    }

    // 마지막 남은 값이 K 이상인지 확인
    return (pq.top() >= K) ? answer : -1;
}

 

풀이

1. scoville 벡터의 원소들을 최소 힙에 삽입한다

🔎 최소 힙을 사용하는 이유

모든 음식의 스코빌 지수를 K 이상으로 만들어야 한다

→ 음식들의 스코빌 지수 중 최솟값이 K 이상이어야 한다는 의미와 같음

→ 최소 힙은 오름차순으로 정렬되므로, pq.top()을 호출함으로써 최솟값을 가져올 수 있다. 이를 통해 최솟값과 K와 비교할 수 있다!

 

2. pq에 최소 두 개의 원소가 있어야 스코빌 지수를 섞을 수 있으므로, pq.size() > 1인 조건을 만족할 때, 가장 작은 두 값을 꺼내 새로 계산된 값을 다시 pq에 삽입한다.

 

3. pq.top() = 현재 스코빌 지수의 최솟값이 K 이상이면 종료한다.