[CodingStudy] Heap -더 맵게

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

프로그래머스_Heap -더 맵게

 

문제 자체는 어렵지 않았는데 효율성에서 막혔던 문제이다.

sort를 매번 반복때마다 사용하게 되면 시간복잡도가 O( N * N logN ) 가 된다.

효율성을 통과하기 위해서는 heapq 모듈을 쓰는 방법이 있었다.

(다른 방법이 있다면 알려주세용..)

 

heapq 알고리즘

heap= 최소/최대 규칙을 따르는 이진 트리

• 최소 힙=부모 노드 값이 자식 노드보다 항상 작거나 같음
• 최대 힙=부모 노드 값이 자식 노드보다 항상 크거나 같음

파이썬에서 힙큐알고리즘(우선순위 큐 알고리즘) 내장 모듈을 제공한다.

즉 따로 정렬을 하지 않아도 가장 낮은 값이 가장 낮은 인덱스에 위치한다.

heapq.heapify(list)	list를 힙으로 변환
heapq.heappush(heaplist, value)	heap에 value값 push (힙 불변성 유지)
heapq.heappop(heaplist)	heap에서 가장 작은 항목 pop (힙 불변성 유지)
heapq.heappushpop(heaplist, value)	heap에 value를 push 후 heap에서 가장 작은 항목 pop (즉 heappush > heappop)
heapq.heapreplace(heaplist, value)	heap에서 가장 작은 항목 pop 및 새로운 value push (즉 heappop > heappush)

 

더 맵게

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래 방식으로 섞음.

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

 

음식의 스코빌 지수를 담은 배열 = scoville, 원하는 스코빌 지수 = K가 주어질 때,

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return.

ex) scoville=[1, 2, 3, 9, 10, 12]  /  K=7 /  return=2

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) 		# heap 구조로 변환

    while True:
        one=heapq.heappop(scoville)	# heap에서 가장 작은 값 반환
        if one >K:			# 모든 스코빌 지수가 K값 이상이 될 때까지
            break
        if len(scoville)==0:		# 더 이상 만들 수 없는 경우
            return -1
        two=heapq.heappop(scoville)	# heap에서 가장 작은 (두번째) 값 반환
        heapq.heappush(scoville,one+two*2)
        answer+=1			# 섞은 횟수

    return answer