[프로그래머스] 더 맵게

코딩테스트 연습 - 더 맵게

풀이

최소 원소를 빠르게 꺼낼 수 있는 방법으로 힙(heap)을 선택했다.
그리고 priority_queue를 사용하여 스코빌 지수가 가장 낮은 음식 두개를 빼와서 새로운 음식을 계속 만들어주면 된다. 만약 가장 작은 음식이 K를 넘었다면 break로 while문을 나가고, 모든 음식들을 다 조합하여 새로운 음식을 만들더라도 K를 넘지 못하면 answer = -1로 해준다.

시간 복잡도

• O(nlogn)

힙(Heap)

• 최대/최소 원소를 빠르게 찾을 수 있음
• 연산
  -> 힙 구성(heapify) N개의 원소를 삽입 O(NlogN)
  -> 삽입(insert) O(logN)
  -> 삭제(remove) O(logN)
• 완전 이진트리로 구현한다 -> 배열을 이용해서 구현이 가능하다

힙의 응용

• 정렬(heapsort)
• 우선 순위 큐(priority queue)

코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    for(auto& it : scoville) q.push(it);

    while(1){
        int num1 = q.top(); q.pop();
        if(num1 >= K) break;
        if(q.empty()){ // 아무리 다 더해도 k를 넘지 못한다.
            answer = -1;
            break;
        }
        int num2 = q.top(); q.pop();
        q.push(num1 + num2 * 2);
        answer++;
    }
    return answer;
}