[프로그래머스] level2 힙 더 맵게

문제링크 : 코딩테스트 연습 - 더 맵게 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 더 맵게 프로그래머스 (programmers.co.kr)

풀이 방법

처음에 큐로 구현하여 2개를 pop하여 가져와서 계산 후 넣어주고 다시 정렬해 주는 방식으로 아래와 같이 구현하였다.

def solution(scoville, K):
    answer = 0
    scoville = deque(sorted(scoville))
    while min(scoville) < K:
        if len(scoville) > 1:
            n, m = scoville.popleft(), min(scoville)
        else:
            return -1
        scoville[0] = n + (m * 2)
        scoville = deque(sorted(scoville))
        answer += 1
    return answer

큐나 스택으로 구현하였을 때, 효율성에서 걸리는 문제가 발생하였다. 그래서 큐나 스택보다 오름차순 정렬에 용이한 heapq를 사용하여 구현하였다.

하지만 heapq를 사용해서 구현해도 효율성 문제에 걸려서 내장함수를 확인하던 중 while문 검사할 때 min을 사용해서 효율성에 걸리는 문제가 있었다. (내 30분... ㅠㅇㅠ)

내장함수 min, max는 시간복잡도 O(N)이라는 걸 명심하자..

 

나의 풀이

풀이 확인

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] <= K:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville)*2)
            answer += 1
        else:
            return -1

    return answer

다른 사람들도 나와 비슷하게 푼 것 같다.