[더 맵게/LV2/Python3, C++]

다리를 지나는 트럭 LV2

 

문제 설명
매운 것을 좋아하는 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

 

알고리즘 고득점 Kit의 힙 문제 중 하나이다.

 

 

힙의 최솟값이 K보다 크거나 같을 때 연산 횟수를 반환한다.

힙이 비었거나, 힙의 크기가 1이고 K보다 작으면 -1을 반환한다.

 

 

#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(auto v : scoville)
        pq.push(v);
    
    int cnt = 0;
    while(!pq.empty() && pq.top() < K)
    {
        if (pq.size() == 1) return -1;
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        pq.push(a + b*2);
        cnt++;
    }
        
    
    return (pq.empty() ? -1 : cnt);
}

 

 

 

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    time = 0
    
    while scoville and scoville[0] < K:
        if len(scoville) <= 1: return -1
        
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a + b*2)
        time += 1

    return time

 

 

---