프로그래머스 68일차 - 더 맵게

from collections import deque

def solution(scoville, K):
    answer = 0
    scoville.sort()
    scoville = deque(scoville)

    while scoville[0] < K:

        num = scoville.popleft() + (scoville.popleft()) * 2
        scoville.insert(0, num)
        answer += 1

        if scoville[0] < K and len(scoville) == 1:
            return -1

    return answer

 

처음에 위처럼 적었다.

근데 deque 특성상 sort를 하려면 리스트로 변환 후 다시큐로 만들어야한다. 그래서 이 코드는 잘못됐다.

 

def solution(scoville, K):
    answer = 0

    scoville.sort()

    while scoville[0] < K:

        num = scoville.pop(0) + (scoville.pop(0)) * 2
        scoville.insert(0, num)
        scoville.sort()
        
        answer += 1

        if scoville[0] < K and len(scoville) == 1:
            return -1

    return answer

그래서 위처럼 deque를 안쓰고 작성했다.

그랬더니 정확성 테스트는 통과했으나, 효율성 테스트는 0점이었다.

그렇다. 이문제는 heap 자료구조를 사용해서 풀라는 문제이다.

 

 

import heapq

def solution(S, K):
    heap = []
    for i in S:
        heapq.heappush(heap, i)

    cnt = 0
    while heap[0] < K:
        heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap) * 2)
        cnt += 1
        
        if len(heap) == 1 and heap[0] < K:
            return -1
    return cnt

코드는 똑같다.

다만 Heap을 쓰면 heap 자료구조 특성상 sort를 자동으로 해주니까 시간효율성이 증가된다.

그걸 이용하라는 뜻이다.