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

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

Solution

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

using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> PQ;
    for(int i = 0; i < scoville.size(); i++) PQ.push(scoville[i]); 
    int count = 0;
    while(PQ.size() > 1 && PQ.top() < K){
        int first = PQ.top();
        PQ.pop();
        int second = PQ.top();
        PQ.pop();
        int result = first + (second * 2);
        PQ.push(result);
        count++;
    }
    if(PQ.top() < K) count = -1;
    return count;
}

우선순위 큐에 대한 지식 뿐만 아니라 이걸 어떻게 써먹어야 하는가? 에 어느정도 통달해야지 풀 수 있는 문제였다. 자료구조에 대한 지식은 대학 공부를 하다보면 어느정도는 쌓이지만 그래서 이걸 어떻게, 잘 쓸 수 있는지는 경험이 많아야 최적의 답안이 나오기 때문이다.
사실 1회차만에 답을 제출하기는 했으나 상당히 무지성으로 코드를 짰단 생각이 들었다.

요구사항을 다시 한번 읽어보자.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

모든 음식들이 어찌되었건 K 이상의 스코빌 지수를 가지면 그만이다. 그러므로 최소힙으로 우선순위 큐를 구성한다.

while(PQ.size() > 1 && PQ.top() < K){
    int first = PQ.top();
    PQ.pop();
    int second = PQ.top();
    PQ.pop();
    int result = first + (second * 2);
    PQ.push(result);
    count++;
}
if(PQ.top() < K) count = -1;
return count;

즉 Top에는 가장 스코빌 지수가 낮은놈이 나온다. 그 두놈을 꺼내서 결과값을 다시 우선순위 큐에 집어넣는다. 이것을 우선순위 큐의 데이터가 2개 이상 있고 top이 K보다 작은 동안 반복한다. 하나의 조건이라도 깨지면 while문이 끝난다. 왜냐면 죽어도 K 이상의 스코빌 지수를 만들 수 없는 데이터도 존재하기 때문이다.

문제 자체는 상당히 단순한 문제다. 우선순위 큐를 잘 모른다면 죽자고 정렬만 했을 문제지만 알고있다면 훨씬 단순하게 해결할 수 있는 문제.