[프로그래머스] 더 맵게

[프로그래머스] 더 맵게

• https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=python3

• vector 자료구조를 사용하는 경우
  while loop을 돌 때마다 내림차순으로 sort해야 함
  -> 시간 초과

• min Heap 자료구조를 사용해야 함

C++ 풀이

• priority queue 사용 (오름차순)

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

using namespace std;

int solution(vector<int> scoville, int K) {
    
    //오름차순 우선순위 큐
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for(int i = 0; i<scoville.size(); ++i){
        pq.push(scoville[i]);
    }
    
    int answer = 0;
    while(pq.size() > 1){
        if(pq.top() >= K){
            return answer;
        }
        long long first = pq.top();
        pq.pop();
        long long second = pq.top();
        pq.pop();
        pq.push(first + (second * 2));
        answer++;
    }
    
    //pq 크기 1일 때 음식의 스코빌 지수 K이상인지 검사!
    if(pq.top() >= K) return answer;
    return -1;
}

Python 풀이

• heapq 사용

from heapq import heappush, heappop

def solution(scoville, K):
    minHeap = []
    for sc in scoville:
      heappush(minHeap, sc)
      
    answer = 0
    while (len(minHeap) > 1):
      if(minHeap[0] >= K):
        return answer
      
      first = minHeap[0]
      heappop(minHeap)
      second = minHeap[0]
      heappop(minHeap)
      heappush(minHeap, first + (second * 2))
      answer += 1

    //pq 크기 1일 때 음식의 스코빌 지수 K이상인지 검사!
    if(minHeap[0] >= K):
        return answer
    return -1

📌참고자료

• 파이썬의 heapq 모듈로 힙 자료구조 사용하기
  https://www.daleseo.com/python-heapq/