[프로그래머스] 더 맵게, level2, heapq, python

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

 

문제 풀이

주어진 scoville 리스트를 활용하여, 각 음식이 주어진 스코빌 지수 K보다 커질 때 까지 음식을 섞어 새로운 음식을 만든다는 이야기다. 새롭게 만든 음식의 스코빌 지수를 리스트에 넣을 때, 별도의 작업 없이 정렬 된 상태의 리스트를 사용할 수 있다면 아주 쉽게 풀이할 수 있다.

 

그렇다면 어떻게 이 문제를 풀이할 수 있을까?

 

heapq

데이터를 정렬된 상태로 저장하기 위해서 파이썬에는 heap 내장 모듈을 지원한다.

 

힙 자료구조는 이진 트리(binary tree)기반의 최소 힙(min heap) 자료 구조를 제공한다. min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, 가장 작은 값은 언제나 인덱스 0, 즉 이진 트리의 루트에 위치한다.

     1  ---> root
   /   \
  3     5
 / \   /
4   8 7

heaqp 모듈은 파이썬의 내장 모듈이기 때문에 간단히 import 후에 사용할 수 있다.

import heapq as hq
from heapq import heappush, heappop...

 

그렇다면 heapq를 사용해서 문제풀이를 해보자!

먼저 주어진 scoville 리스트를 힙 자료구조로 바꿔준다.

#1
heapify(scoville)

#2
heap = []
for i in scoville:
	heappush(heap, i)

리스트를 힙 자료구조로 바꿔주는 방법은 2가지가 존재하는데, 첫 번째 방법은 heapify 함수를 이용해서 scoville 리스트를 힙 자료구조로 바꿔줄 수 있다. 두 번째 방법은 for문을 돌며 생성한 heap 리스트에 heappush 함수를 사용하여 하나씩 원소를 넣어주는 방법이다.

 

 

이제 항상 정렬된 리스트를 얻었으니 문제에서 설명해 놓은대로 풀이만 해준다면 끝!

from heapq import heappush, heappop, heapify

def solution(scoville, K):
    answer = 0
    
    # 힙 자료구조로 변경
    heapify(scoville)
    
    # 가장 작은 스코빌 지수가 K보다 작을 때까지 while
    while scoville[0] < K:
        
        # 가장 작은 스코빌 지수
        dish = heappop(scoville)
        
        # 두 번째로 작은 스코빌 지수
        dish2 = heappop(scoville)
        
        # 새로운 음식
        new_dish = dish + (dish2 * 2)
        
        # 힙 리스트에 다시 넣어준다.
        heappush(scoville, new_dish)
        
        # 섞은 횟수 +1
        answer += 1
        
    	# 모든 음식이 섞였다면 while문 종료 (모든 음식을 K이상으로 만들 수 없을 경우)
        if len(scoville) < 2:
            break
    
    if scoville[0] >= K:
        return answer
    else:
        return -1

 

문제 풀이할 때 참고한 글이다!

https://www.daleseo.com/python-heapq/

파이썬의 heapq 모듈로 힙 자료구조 사용하기