프로그래머스[Lv.2] - 더 맵게

문제 설명

매운 것을 좋아하는 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 합니다.

---

 

 

 

 

 

 

풀이

가장 작은 수와 그다음 작은 수를 이용해 K를 넘겨야 하는 문제이다.

따라서, 정렬이 되어야 한다.

그리고 작은 두 수를 꺼내 큰 수를 만들었다고 해도 기존의 수보다 작을 수 있고 K를 넘지 않을 수 있다.

즉, 새로운 수를 만들 때마다 정렬이 되어야 한다는 뜻이다.

이런 특성을 생각해 보면 유용한 자료구조가 있다.

priority_queue(pq)이다.

pq는 Heap을 기반으로 만들어졌다.

삽입, 삭제에 O(logN), 최솟값을 찾는 과정에서는 O(1)이 소요된다.

따라서, 문제없이 통과할 수 있다.

---

 

 

 

 

 

전체 코드

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

using namespace std;


int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(auto s : scoville)
    {
        pq.push(s);
    }
    
    while(!pq.empty())
    {
        int small = pq.top();
        pq.pop();
        
        if(small >= K) break;
        
        if(!pq.empty())
        {
            int next = pq.top();
            pq.pop();

            pq.push(small + next*2);
            answer++;
        }
        else
        {
            answer = -1;
            break;
        }
    }
    
    return answer;
}

---