• 힙 알고리즘 문제 : 프로그래머스 LEVEL 2(더 맵게) image - 사용 언어 : C++ - 해결 날짜 : 2021-01-26

    **- 해결 방법** :

    처음에는 우선순위 큐를 사용하지 않고 정렬을 수행한 뒤 삭제,삽입의 과정으로 해결하려 하였는데,
    실행시간 오류가 발생하여 우선순위 큐를 활용하였다.

    오름차순으로 저장하여 최하위 값 두개에 대한 접근, 삭제를 용이하게 하였다.

    우선 우선순위 큐 pq의 제일 작은 값이 K보다 작은 동안 반복하며 최하위 두 개에 대한 스코빌 지수를
    섞으며 answer를 증가시켰고, 섞는 동안 size가 1이 되면 멈추도록 하였다.

    반복문 종료 후 사이즈는 1이고, 남은 음식의 스코빌 지수가 K보다 작다면 K 이상으로 만들기에 실패한
    경우 이므로 -1을 반환하였고, 아니라면 정상적인 answer를 반환하도록 문제를 해결하였다.


- 코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    //우선순위 큐 pq에 오름차순으로 저장
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 0; i<scoville.size(); i++){
        pq.push(scoville[i]);
    }

    //pq의 top(제일 작은 값)이 K보다 작은 동안 반복
    while(pq.top() < K){
        if(pq.size() == 1) break; //pq의 size가 1이면 break
        int first_min = pq.top(); //현재 pq의 최소 값
        pq.pop();
        int second_min = pq.top(); //현재 pq의 두번째 최소 값
        pq.pop();

        pq.push(first_min+second_min*2); //음식 섞기
        answer++;
    }
    //사이즈가 1인데 남은 음식의 스코빌 지수가 K보다 작다면 K 이상으로 만들기 실패한 경우
    if(pq.top() < K) return -1;
    return answer;
}
```