[힙(Heap)] Level 2 더 맵게

문제 설명

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

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

 

입출력 예시 및 설명

---

(풀이)

딱 보자마자 이거 힙 안쓰고 배열로도 풀겠는데?? 했다가 탈탈 털림 ㅋ_ㅋ

배열로 푸니까 시간 엄청 오래걸리더라,,,

혹시 sort 떄문에 오래걸리나 싶어서 reverse로도 해보고, pop(0)가 오래걸린다길래 다 해봤는데

음음 역시 답은 힙이었어

힙으로 하니까 겨우 통과됨

 

 

파이썬 코드)

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while True:
        if len(scoville) < 2:
            answer = -1
            break

        one = heapq.heappop(scoville)
        two = heapq.heappop(scoville)
        mix = one + (two * 2)
        heapq.heappush(scoville, mix)
        answer += 1
        if scoville[0] >= K:
            break
        
    return answer

우선 heapq.heapify로 scoville 리스트를 힙으로 만든다

그리고 문제 조건 중 scoville의 길이는 2 이상이라고 했으니까 길이가 2보다 작을 경우 break

min heap이기 때문에 heappop으로 두 개를 꺼내면 최솟값 2개가 나온다

그걸로 섞은 매운 맛을 계산하고 다시 heap에 넣어준다

그리고 scoville[0]으로 최솟값을 확인해서 이게 기준 K를 넘는지 확인하도록 하였다

알고리즘은 쉬운편인듯!!

 

 

C++ 코드)

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    
    while(pq.size()>=2 && pq.top()<K)
    {
        answer++;
        int one = pq.top();
        pq.pop();
        int two = pq.top();
        pq.pop();
        pq.push(one + two*2);
    }
    if(pq.top()<K) //모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
    {
        answer = -1;
    }
    return answer;
}

c++에서는 우선순위 큐를 사용하여 구현하였다

이 때 우선순위 큐는 기본적으로 내림차순으로 정렬되기 떄문에 오름차순으로 정렬하도록 선언한다

그리고 큐의 크기가 2이상이고, 가장 최솟값인 pq.top()이 K보다 작을때만 연산을 수행한다

앞에 2개 꺼내서 계산하고 다시 넣고 반복!

만약에 while문을 탈출했는데도 pq.top()이 K보다 작으면 모든 음식의 스코빌 지수를 K이상으로 만들 수 없으므로 -1을 반환한다

 

 

휴 c++이 빠르긴 한데 나 자꾸 파이썬한테 흔들려,,,

날 붙잡아줘 c++,,,

근데 파이썬 안하겠다는 건 아님ㅋ

암튼 빠잉~