[프로그래머스] [힙(Heap)] Lv.2 /더 맵게 (파이썬/Python)

1. 문제 설명

2. 코드 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    count = 0
    
    while scoville:
        least = heapq.heappop(scoville)
        if least >= K:
            return count
        if not scoville:
            return -1
        second_least = heapq.heappop(scoville)
        new_food = least + (second_least * 2)
        heapq.heappush(scoville, new_food)
        count += 1
    return -1

3. 풀이 과정

• 자투리 상식 : Heap(힙)이란?
  - 특정한 규칙을 만족하는 이진 트리(Binary Tree) 자료구조
  - 최소 힙(Min-Heap) : 부모 노드가 항상 자식 노드보다 작거나 같다.
  - 최대 힙(Max-Heap) : 부모 노드가 항상 자식 노드보다 크거나 같다.
• Heapq 모듈
  - 리스트를 힙처럼 사용할 수 있는 기본 라이브러리
  - 기본은 최소 힙(min-heap)으로 동작
  - 가장 작은 원소를 빠르게 삽입/삭제할 수 있다.
• 주요 함수
  1) heapify()
  - 주어진 리스트를 한 번에 힙 구조로 변환
  2) heappop()
  - 힙에서 가장 작은 원소를 꺼낸다.
  - 가장 작은 값이 제거되고, 남은 리스트도 힙 구조를 유지한다.
  3) heappush()
  - 힙에 새로운 원소를 추가한다.
  - 추가한 후에도 힙 구조를 유지하도록 재정렬한다.

리스트를 힙 구조로 변환시키기 위해 heapq 모듈을 import한다.

scoville 리스트를 heapify()로 힙 구조 변환을 한다.

카운트 변수 count를 0으로 초기화한다.

scoville 값이 존재하면 반복하는 while문을 시작한다.

least 변수에 heappop()으로 최솟값을 빼서 입력시킨다.

least가 K보다 그거나 같으면 count값을 반환한다.

scoville 에 값이 없으면 -1을 반환한다.

두번째 작은 수 second_least에 heappop()으로 scoville의 두번째 최솟값을 넣는다.

new_food변수에 least와 second_least의 두배를 더한 값을 넣는다.

heappush()로 scoville에 new_food값을 추가한다.

count 값에 1을 더한다.

scoville에 값이 비어버려 while문을 빠져나오면 -1을 반환한다.

4. 추천 코드

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

 

5. 추천 코드의 풀이 과정

나의 코드와의 차이점만 비교하면

heapq 모듈을 hq로 짧게 표현

while True로 무한 반복문 작성

최솟값이 K보다 크거나 같으면 break로 반복문을 빠져나와 answer값을 반환한다.

len(scoville)값이 비어버리면 -1을 반환한다.

while문의 조건의 차이로 코드 달라졌다.