더 맵게

첫번째 코드

 

prioirty queue를 이용해서 정렬한 후 맨 앞과 그 다음을 뽑은 후 계산해서 넣는 과정을 반복해서 계산하도록 하였다.

 

from queue import PriorityQueue

def solution(scoville, K):

    prioirty = PriorityQueue()

    count = 0

    for i in scoville:
        prioirty.put(i)

    while not prioirty.empty() and prioirty.queue[0] < K:
        least = prioirty.get()
        if least >= K:
            continue
        else:
            mixed = prioirty.get()
            new_scoville = least + mixed * 2
            count += 1
            prioirty.put(new_scoville)

    return count

 

하지만 해당 코드는 일부에서 시간 초과가 발생하였다.

---

두번째 코드

 

내 예상에 priority queue를 만드는 데에 반복하는 계산을 제거할 수 있을 것 같았다.

하여 heap 방법을 이용하여 코드를 작성한다.

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    count = 0

    while len(scoville) > 1 and scoville[0] < K:
        least1 = heapq.heappop(scoville)
        least2 = heapq.heappop(scoville)
        new_scoville = least1 + least2 * 2
        heapq.heappush(scoville, new_scoville)
        count += 1

    if scoville[0] < K:
        return -1

    return count

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42626.%E2%80%85%EB%8D%94%E2%80%85%EB%A7%B5%EA%B2%8C

programmers/프로그래머스/2/42626. 더 맵게 at main · ornni/programmers