[C++] 프로그래머스 : 더 맵게

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

bool flag = true; // 모든 음식 스코빌 지수 넘었는지 여부
int cnt = 0; // 섞은 횟수
priority_queue<int, vector<int>, greater<int>> pq; // 오름차순 정렬

int solution(vector<int> scoville, int K) {
    int answer = -1;
    
    for(int i = 0; i < scoville.size(); i++){
        pq.push(scoville[i]); // 우선순위 큐에 스코빌 지수 넣기 - 자동 정렬
    }
    
    // 스코빌 지수 K 값 안될 경우
    while(pq.size() > 1 && pq.top() < K){
        int front = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();

        pq.push(front + second * 2);
        cnt++;
    }
    
    // 더 이상 섞을 수 없는 경우
    if(pq.size() == 1 && pq.top() < K){
        return answer;
    }
    
    return cnt;
}

우선순위 큐는 힙으로 풀 수 있다.

• 처음에는 정렬이 필요하다고 생각해서 vector를 sort해서 풀려했지만 힙문제니 우선순위 큐로 풀어보기로 하였다.

• 프로그래머스와 기존 사용하던 vs Code에서의 환경이 달라 vsCode의 컴파일러가 허용하던 "큐 반복문으로 순회" 와 같은 것들이 되지 않아 좀 애를 먹었다. 아무래도 야매코딩을 하고 있었나보다. 큐는 while을 이용해서 탐색해주어야한다. K값을 넘는지만 알아보면 되므로 우선순위 큐의 성질인 자동 정렬을 이용해 제일 앞의 값이 K가 넘는다면 모든 값이 K 이상이 됨을 알 수 있다. 수학적으로 생각하자! 계속 정렬이 된다.

• 우선순위 큐를 이용해 스코빌 지수를 우선순위 큐에 넣으면 자동으로 정렬이 된다. 여기서 정렬은 내림차순이 default 값이라 오름차순을 위해서는

priority_queue<int, vector<int>, greater<int>> pq; // 오름차순 정렬

을 사용한다.

• 우선순위 큐에서 첫번째 값은 pq.top()이다. pq.front()가 아니다.

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우는 음식이 1가지 남았고 해당 음식의 스코빌 지수가 K가 되지 않았을 때이다.