[Python] 프로그래머스 - 더 맵게 | heapq 동작 원리

나의 풀이

import heapq
 
def solution(scoville, K):
    answer = 0
    scoville.sort()    # 빠뜨리지 말자
 
    while scoville[0] < K:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)
            answer += 1
        else:
            answer = -1
            break
 
    return answer

처음에는 list.sort()로 접근 하다가 효율성 케이스 실패로, heapq로 변경. 그런데 while문 타기 전 최초에 한번은 리스트 정렬을 해줘야하는데, 그걸 빠뜨려서 테스트 케이스에서 계속 몇 개가 삐꾸 났다. 실제 코테 상황에는 이런 사소한 부분이 오히려 발견하기 어려워서 당황할 것 같음. 그리고 문제 푸는 시간이 너무 오래 걸려서 큰일이다... 1일 3솔씩 처리해야할 것 같음.

 

다른 사람의 풀이

다른 사람들도 대부분 heapq로 풀어서 비슷하게 나왔다. binary heaps 한번 정리하고 감.

- Heap :
최소값 또는 최대값을 빠르게 탐색하기 위한 완전이진트리 자료구조. 최소힙은 최소값이 root에 위치, 최대힙은 최대값이 root에 위치한다.

- 요소 추가 :
새로운 요소를 마지막 leaf에 추가하고, 자신의 부모 노드와 값을 비교해 계속해서 부모와 자리를 바꿔가는 방식으로 동작. 최소힙의 경우, 새로운 요소가 부모 노드보다 클 때 또는 root에 도착할 때에 탐색이 종료된다.

- 요소 삭제 :
요소를 삭제하고, 삭제된 요소의 자리에 해당 트리의 맨 마지막에 있는 요소를 가져옴. 그리고 그 가져온 마지막 노드와 자신의 자식 노드와 값을 비교해 계속해서 자식과 자리를 바꿔가는 방식으로 동작. 최소힙의 경우, 가져온 마지막 노드가 자식 노드보다 작을 때 또는 마지막 leaf에 도착할 때에 탐색이 종료된다.

 

https://www.youtube.com/watch?v=jfwjyJvbbBI

https://docs.python.org/ko/3.9/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.9.6 문서