[코딩테스트] 프로그래머스 - 더 맵게 (Lv.2) in Python

스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return.

 

모든 음식 스코빌 지수를 K이상으로 만들기 위해, 가장 낮은 스코빌 지수를 가진 음식을 섞어 새로운 음식을 만든다. 이 때,

 

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

 

 

프로그래머스 강의 내용을 바탕으로 풀이합니다.

 

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

 

풀이

- 가장 맵지 않은 두 음식을 골라야 하므로, sorting은 필수!

- 다만 최악의 경우 (n-1) - 전체 음식 수를 n이라고 할 때 - 번 섞어야 하는데,

- 섞을 때마다 순서를 맞춰 삽입해야한다면 알고리즘 복잡도는 O(n^2)가 됨.

 

- 최소/최대 원소를 힙(Heap)을 사용하여 빨리 꺼내자.

 

힙 (Heap)

- 완전 이중 트리 (Complete Binary Tree)의 일종

- 최댓값 혹은 최솟값을 찾기에 용이 (최댓값 및 최솟값은 항상 max heap / min heap의 root에 위치하기 때문)

- 느슨한 정렬을 이룸

~> parent node 값이 child node 값보다 항상 크거나 (max heap) 작은 (min heap) 상태

- 중복된 값 허용

- 우선순위 큐 (priority queue) 구현에 사용

 

파이썬 내의 힙 / 힙 큐 (Heap)

import heapq

참고 - docs.python.org/3/library/heapq.html

 

주의점

- zero-based indexing, 인덱싱이 0부터 시작한다. 파이썬의 다른 자료구조와 통일성을 갖추기 위함.

- min heap 최소 힙 구현하는 모듈임!

 

heapq.heapify(x)
# 리스트 x를 linear time 내에 min heap으로 구조화 시킴.
# O(n log n)

heapq.heappush(heap, item)
# min heap 구조를 지키면서, heap에 item을 추가함.
# O(log n)

heapq.heappop(heap)
# min heap 구조를 지키면서, 최솟값을 반환함.
# heap에서 item을 빼지 않고 최솟값을 참조하려면, heap[0] 사용
# heap이 비어있다면 IndexError를 일으킴
# O(log n)

heapq.heappushpop(heap, item)
# push 와 pop을 동시에 함
# 이 때, push할 값과 pop할 값 중 더 작은 값을 pop함

heapq.heapreplace(heap, item)
# 위와 기능 동일
# 다만, push할 값과 pop할 값의 비교 없이 무조건 heap에 있던 값을 pop하고, item을 push함

이 외에도 몇 가지 functions 가 더 있다.

 

 

 

파이썬 구현

import heapq

def solution(scoville, k):
    answer = 0
    heapq.heapify(scoville)
    
    while True:
    	food1 = heapq.heappop(scoville)
        
        if food1 >= K:
        	return answer
        elif len(scoville) == 0:
        	return -1
            
        food2 = heapq.heappop(scoville)
        
        heapq.heappush(scoville, food1 + 2 * food2)
        answer += 1