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

문제

더 맵게 : 문제 링크

문제 분석

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

  섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

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

• 여기서 scoville의 길이는 2 이상 1,000,000 이하, K는 0 이상 1,000,000,000이하, scoville의 원소는 각각 0 이상 1,000,000 이하이다. 일반적인 vector나 deque로 풀게되면 정답은 맞아도 시간 효율성에서 초과될 수 있음을 생각해야함.

• 바탕 컨테이너로 vector를 사용하는 오름차순의 우선순위 큐(priority_queue)를 사용했고, for loop를 사용하여 scoville의 원소를 que로 복사하였다. while loop는 que 크기가 1보다 크고, que의 top이 즉 que[0] 위치의 원소가 K보다 작은 동안 작동된다. 섞는 횟수 answer을 1 더해주고, int 변수 a, b에 que[0], que[1] 각각을 저장 후 pop 시킨다. 그 후, 위의 방법대로 (a + b * 2)를 연산한 값을 push하고 그 과정을 반복한다.

• while loop가 끝나고 마지막 남은 원소가 K보다 작으면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 이므로 -1을, 이외의 경우는 answer을 return 한다.

우선순위 큐(priority_queue)
우선순위 큐는 선입선출 순이 아니라 우선순위가 높은 항목이 가장 앞에 오도록 하는 큐이다. 우선순위가 같은 항목들 사이에서도 선입선출 순을 보장하지 않고, 헤더에 함께 정의 되어 있고 정의는 다음과 같다.

template <typename _Ty, typename _Container = vector<_Ty>, typename _Pr = less<_Ty>>
class priority_queue;

두 번째 파라미터가 바탕 컨테이너이며 vector 외에도 deque을 사용할 수 있다. 세 번째 파라미터는 우선순위의 비교에 사용될 비교 연산을 나타내는 타입이다. less 템플릿 또는 greater 템플릿의 인스턴스가 오거나 클로져와 같은 function이 올 수 있다.

풀이

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0, a = 0, b = 0;
    
    priority_queue<int, vector<int>, greater<int>> que;
    for(int i = 0; i < scoville.size(); i++) que.push(scoville[i]);
    while(que.size() > 1 && que.top() < K) {
        answer++;
        a = que.top();
        que.pop();
        b = que.top();
        que.pop();
        que.push(a + b * 2);
    }
    if(que.top() < K) answer = -1;
    return answer;
}