[프로그래머스] Level 2 - 더 맵게 (Python)

 

 

 

 

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

코딩테스트 연습 - 더 맵게

 

 

 

 

✅ Solution

• 가장 작은 값에 반복적으로 접근해야 하므로 heapq 모듈을 사용한다.
• heapq의 heapify를 이용하여 scoville 배열을 최소 힙 자료구조로 변환한다.
• 가장 작은 스코빌 지수가 k보다 작다는 조건을 이용하여 반복문을 돌린다. 
  • 반복문에서는 가장 작은 스코빌 지수와 두 번째로 작은 스코빌 지수를 heapq.heappop()을 이용해 구해 mix 변수에 할당하여, 다시 heappush()를 이용하여 넣어준다. 
  • 만약 스코빌 지수의 길이가 1이라면 스코빌 지수의 값을 모두 더해 한 개 원소가 남았는데, 그 원소가 k이상 되지 않는 것을 의미하기 때문에 -1을 리턴한다.

 

 

 

 

✅ Code

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)

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

        mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, mix)
        answer += 1

    return answer

 

 

 

 

📝 Today I Learned

heapq

• heap이 heapq 배열이라고 할 때, heap[0] 은 최솟값을 의미하지만 heap[1], heap[2]의 경우 두 번째로 작은 원소, 세 번째로 작은 원소임을 보장하지 않는다.
• heapq 모듈은 원소를 삭제할 때마다, 즉 heappop() 함수 호출 시에 이진트리 재배치가 이뤄지고, 이때 최솟값을 heapq[0]에 위치시키기 때문이다.
• 따라서 두 번째, 세 번째 작은 원소를 구하기 위해서는 heappop()을 이용하여 첫 번째 원소에 접근하는 방식으로 구해야 한다.