[코딩테스트] 프로그래머스 더 맵게 파이썬(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

import heapq
def solution(scoville, K):
    count = 0
    heapq.heapify(scoville)
    while True:
        a = heapq.heappop(scoville)
        if a >= K:
            return count
        if len(scoville) < 1:
            return -1
        b = heapq.heappop(scoville)
        c = a + (b * 2)
        heapq.heappush(scoville, c)
        count += 1

저는 heapq 모듈을 import하여 최소힙(min heap)자료구조를 사용해서 문제를 해결하였습니다.

자세한 내용은 파이썬 공식문서에 나와있고, 문제를 풀 때 참고 했던 링크를 첨부하겠습니다.

heapq — Heap queue algorithm

 

최소힙은 값을 push하면 부모 노드는 자식노드 보다 더 작거나 같은 값을 같게 되고

이 특성을 이용하여 문제를 해결할 수 있었습니다.

• 최소힙 자료구조는 부모 노드가 자식 노드보다 작거나 같은 값을 갖는 이진 트리 구조이기 때문입니다.

heapq.heapify()로 주어진 scoville 리스트를 최소힙 자료구조 형태로 만들어줍니다.

while문으로 반복을 하면서

먼저 heapq.heappop() 함수로 부모 노드의 값을 꺼내게 됩니다.

이 값을 a라고 하겠습니다.

 

이 a값이 주어진 K보다 크거나 같다면 지금까지 계산된 count 값을 반환하면서 함수를 종료합니다.

최소힙의 자료구조 상 루트노드(최상단노드)의 값이 가장 작기 때문에 그 다음 노드를 볼 필요가 없습니다.

즉 가장 작은 값이 주어진 K보다 크거나 같다면 뒤를 볼 필요도 없는 것입니다.

 

그리고 남은 scoville 리스트의 크기가 1보다 작다면 모든 음식을 K이상으로 만들 수 없기 때문에 -1을 반환합니다.

 

위의 모든 조건문을 통과했다면

b 를 꺼내어

a + (b * 2)를 계산해주고 다시 최소 힙 자료구조에 push해주고 count + 1로 값을 증가시켜줍니다.

• push를 하게 되면 내부적으로 최소 힙 자류구조에 맞게 데이터의 순서가 정렬이 됩니다.