프로그래머스 - 더 맵게(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

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

접근 방법

문제의 카테고리 자체가 heap, 우선순위 큐로 되어 있는데 우선 단순한 list와 sort를 사용해도 가능할 것 같아 시도를 해보았다. 다만 어디서 꼬인 건지는 몰라도 효율성 문제가 아니라, 아예 오답이 너무 많이 나와서 파이썬의 우선순위 큐는 어떤 것을 활용하면 되는지 알아보니 heapq 라는 것이 있다는 걸 확인할 수 있었다.

heap 자료구조

heap은 최소, 최대값을 빠르게 구하기 위한 완전 이진 트리 형태의 자료구조이다. Min heap, Max heap이 존재하는데, 이름에서 보이듯이 전자는 작은 것을 위에, 후자는 큰 것을 위에 두는 형태이다. 만약 새로운 삽입이 일어나면, 우선 완전탐색트리의 형태를 유지하기 위해 비어있는 공간 주에 가장 상단에 배치하고, 자신의 부모 노드와 비교하며 자리를 이동한다. 이런 이유로 삽입이 발생하면 최대 시간 복잡도는 O(log N)이 된다. 결국 늘 가장 상단인 root에 최대, 최소값이 배치하게 되는 자료구조이기 때문에 크기에 따라 우선순위를 정해야하는 작업에 사용하면 유용하다.

풀이

import heapq

def solution(scoville, K):
    que = []
    count = 0
	# heap에 데이터를 넣어준다.
    for s in scoville:
        heapq.heappush(que, s)
	# 가장 작은 수가 앞에 있기 때문에, 첫번째가 K보다 크다면 모든 것이 조건에 부합하기 때문에 종료하면 된다.
    while (que[0] < K and len(que) > 1):
        if (len(que) == 2):
		# 계속 섞다가 2개가 남은 시점에서 섞어도 K를 넘지 못했다면 -1 반환
            if (heapq.heappop(que) + heapq.heappop(que) * 2) < K:
                return -1
            else:
                return count + 1
	# 앞의 2개를 꺼내 섞어준다. 섞은 값을 다시 넣으면 알아서 제 위치를 찾아 넣어진다.
        mix = heapq.heappop(que) + heapq.heappop(que) * 2
        heapq.heappush(que, mix)
        count += 1
    return count

 

참고자료

[kata][python] 프로그래머스 - 더 맵게

[자료구조 알고리즘] Binary Heaps (Min-Heaps and Max-Heaps)