[Programmers] 더 맵게

프로그래머스 코딩테스트 문제 중 힙(heap)를 이용해야하는 문제 더 맵게에 대해 파이썬으로 해결한 풀이와 해설입니다.

 

문제 링크

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

코딩테스트 연습 - 더 맵게

 

solution

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    try:
        cnt = 0
        while scoville[0] < K:
            min_1 = heapq.heappop(scoville)
            min_2 = heapq.heappop(scoville)
            new_n = min_1 + 2*min_2
            heapq.heappush(scoville, new_n)
            cnt += 1
        return cnt
    except:
        return -1

 

해설

 

힙은 우선순위 큐 알고리즘이라고도 부르는데요, 모든 k에 대해 heap[k] <= heap[2*k + 1] 과 heap[k] <= heap[2*k+2]인 배열을 사용합니다. 큰 특징 중 하나는 가장 작은 요소가 항상 루트인 heap[0]라는 것입니다.

 

이를 파이썬에서 구현하기 위해 heapq라는 라이브러리가 존재하고 다음과 같이 활용할 수 있습니다.

파이썬의 heapq 라이브러리에서 heapify라는 함수를 사용하면 리스트를 힙의 구조로 변환할 수 있습니다. 그 후 heappop이라는 함수를 사용하면 힙의 불변성을 유지하면서 힙의 루트인 heap[0]인 요소를 빼낼 수 있습니다. 또한, heappush라는 함수를 통하여 원하는 값을 힙 구조에 삽입할 수 있는데요, 이때도 마찬가지로 힙의 불변성이 유지가 됩니다.

 

이를 문제에 적용해본다면 다음과 같습니다.

1. 먼저 scoville 리스트를 힙 구조로 만들어준 후 카운터 변수를 지정해 놓습니다.

2. try, except구문을 활용한 구조를 활용해 줍니다.

3. try 구문일 경우

• 3-1. scoville의 최소값이 스코별 지수 K보다 작을 동안 scoville 지수에서 heappop을 두 번 해주어 최소값 1, 2를 빼냅니다.
• 3-2. 빼낸 두 수에서 섞은 음식의 스코빌 지수를 구한 후 scoville에 heappush 해준 후 카운터 변수를 1 증가시킵니다.

4. except 인 경우 (모든 음식의 스코빌 지수를 만들 수 없을 경우) -1을 return합니다.

 

 

 

-히비스서커스-