[Programmers / C++] 더 맵게 // priority_queue

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 합니다.

 

---

 

입출력 예

 

 

scoville

K

return

[1, 2, 3, 9, 10, 12]

7

2

 

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

---

 

풀이

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> scoville, int K)
{
    int answer = 0;
    priority_queue<int,vector<int>,greater<int>> Q(scoville.begin(),scoville.end());
    
    while(Q.size() > 1 && Q.top() < K)
    {
        int fMin = Q.top();
        Q.pop();
        int sMin = Q.top();
        Q.pop();
        
        Q.push(fMin + (sMin*2));
        answer++;
    }
    
    if(Q.top() < K)
        answer = -1;
    
    return answer;
}

 

 

문제 분류가 힙으로 되어있어, 어떻게 풀어야하나 고민을 해보았는데

우선순위 큐가 힙을 통해서 구현이 가능하다는 점이 생각났고, 따라서 우선순위 큐로 문제를 풀어보았다.

 

우선 내림차순으로 구성되는 우선순위 큐를 생성하고, Q가 1보다 크며 Q의 끝 원소가 K보다 크지 않을 때까지 while문을 실행한다.

while 내부에서는 우선순위 큐 상단의 2개를 팝한 뒤 문제 공식에 따라 Scoville을 섞어주며, 한 번 Mix가 실행되었기 때문에 answer를 증가시켜준다.

 

위와 같은 행동을 반복한 뒤

만약 모든 원소를 섞었음에도 K보다 높은 스코빌을 만들지 못했을 경우 -1, 그렇지 않다면 answer를 반환한다.

 

우선순위 큐에 대한 STL 정보는 아래 블로그를 참조하였다.

 

https://twpower.github.io/93-how-to-use-priority_queue-in-cpp

[C++] C++ STL priority_queue 기본 사용법과 예제