[프로그래머스] 더 맵게

문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/42626

 

 

📋 문제

매운 것을 좋아하는 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 합니다.

 

 

💡 사용된 개념

✔️ 힙

힙(Heap)은 특정한 규칙을 가지는 트리이다.

특정한 규칙은 A가 B의 부모노드이면 A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다는 것이다.

이러한 규칙에서 볼 수 있듯이 힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리이다.

 

힙은 최소힙(Min Heap)과 최대힙(Max Heap)으로 나뉜다.

 

최소힙(Min Heap)

• 부모 노드의 키 값이 항상 자식 노드의 키 값보다 작은 힙이다.
• root의 값이 최소값이다.
• 오름차순 우선순위를 사용하며 가장 작은 요소의 우선순위가 제일 높다.

최대힙(Max Heap)

• 부모 노드의 키 값이 항상 자식 노드의 키 값보다 큰 힙이다.
• root의 값이 최대값이다.
• 내림차순 우선순위를 사용하며 가장 큰 요소의 우선순위가 제일 높다.

 

출처 : https://www.geeksforgeeks.org/heap-data-structure/

 

✔️ heapq

파이썬에서는 heapq 모듈을 통해 heap을 사용할 수 있다.

heapq 알고리즘은 최소힙의 형태를 가지고 있다.

 

값 삽입(push)

heapq.heappush(heap, item)

 

힙의 불변성을 유지하며 item의 값을 heap에 삽입한다.

 

값 제거(pop)

heapq.heappop(heap)

 

힙의 불변성을 유지하며 heap에서 가장 작은 항목을 제거하고 이 값을 반환한다.

가장 작은 항목이 제거되는 이유는 heapq가 최소힙이어서 가장 작은 값이 우선순위가 제일 높기 때문이다.

힙이 비어있으면 IndexError가 발생한다.

 

힙 변환

heapq.heapify(x)

 

리스트 x를 힙으로 변환한다.

 

 

📝 풀이

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
      if len(scoville) >= 2:
        first, second = heapq.heappop(scoville), heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)
        answer += 1
      else:
        return -1
    
    return answer

 

heap을 사용하기 위해 heapq 모듈을 불러왔다.

그리고 입력받은 scoville 리스트를 힙으로 바꿔준다.

 

scoville의 첫 번째 값이 K이상이면 scoville 내의 모든 요소가 K 이상의 값을 가지고 있다는 뜻이다.

따라서 scoville[0] >= K가 될 때까지 while문을 돈다.

 

while문 안에서는 scoville의 값을 바꿔주는 작업을 한다.

heapq가 최소힙이므로 heappop()을 했을 때 가장 맵지 않은 음식은 first에 들어가고 그 다음으로 맵지 않은 음식은 second에 들어간다.

규칙에 따라 first와 second 음식을 섞어 새로운 음식을 만들고 이를 다시 scoville에 넣어준다.

그리고 횟수를 카운트하기 위해 count에 1을 더해준다.

 

만약 while문 안에서 scoville의 길이가 2 이상이 아니라면 K 미만의 스코빌 지수를 가진 값이 있음에도 더이상 섞을 음식이 없다는 뜻이다.

따라서 이 경우 -1을 리턴한다.

 

 

🔍 참조

heapq https://littlefoxdiary.tistory.com/3

heapq method https://docs.python.org/ko/3/library/heapq.html

difference between minheap and maxheap https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/