프로그래머스 - 더 맵게

더 맵게

이 문제는 heap 관련 문제이다
heap은 heap property를 만족시키는 완전이진트리이다.

여기서의 heap property는
부모 노드의 키 값과 자식 노드의 키 값 간의 대소관계를 의미한다.

부모 노드의 key값이 자식 노드의 key값 보다 항상 크다면 최대 힙
부모 노드의 key값이 자식 노드의 key값 보다 항상 작다면 최소 힙
이라고 한다.

힙을 바탕으로 queue를 만든게 우선순위 큐(priority_queue)
이다.

c++의 queue 헤더에 존재한다.

#include<queue>
priority_queue<int> q; // int형 key값 저장하는 최대 힙을 큐로

우선순위 큐는 기본적으로 최대 힙이다.
queue의 top , 즉 트리의 root node가 트리 전체에서의 최대값이다.

물론 이 문제에서는 최소 힙이 필요하다.
최소를 만드는 방법은 두 개가 있다.

1. 더 작은 값을 찾는 비교함수 작성해서 넣기
   ex)

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

처럼 쓰면 된다. 이러면 최소 힙을 갖는 queue가 된다.

2. 키 값을 음수로 저장하자.
   음수로 저장하면 절대값이 가장 작은 값이 가장 큰 값이 되므로 이 값들이 계속 queue의 top이 된다.
   실제로 적용 할 때는 다시 양수로 바꿔서 풀면 된다.
   모든 값이 양수일 때 사용하는 case, 예를 들면 모든 간선의 거리가 양수일 때 만 사용할 수 있는 다익스트라 알고리즘 같은 경우에서 사용할 수 있다.

물론 이 문제에서는 모든 원소의 값이 0 이상임이 보장되므로,
그냥 아무 방법이나 써도 될 것이다.
나는 1번을 이용하였다. 왜냐면 꾸준히 2번을 사용했기 때문

소스코드

#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=0;i<scoville.size();i++){
        q.push(scoville[i]);
    }
    int answer = 0;
    while(!q.empty()){
        int a = q.top();
        if(a>=K) break;
        q.pop();
        if(q.empty()) break;
        int b = q.top();
        q.pop();
        q.push(a+2*b);
        answer++;
    }
    if(q.empty()) return answer=-1;
    return answer;
}

최소 힙 외에도, 이 문제는 queue의 underflow 또한 생각해줘야 하긴 한다.