Level 2 더 맵게 Python3

https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 

코딩테스트 연습 - 더 맵게

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_더맵게.py

hwayeon351/Programmers-Algorithms

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

---

풀이 과정

풀이 시간 22분

스코빌 지수 순으로 scoville을 오름차순으로 정렬하여 스코빌이 가장 낮은 두 음식을 pop()하여 섞어 준 후 scoville에 추가해 나가면 된다. 두 음식을 섞어서 새롭게 나온 스코빌 지수를 scoville에 추가한 이후에도 스코빌 지수 순으로 오름차순으로 정렬되어 있어야 한다.

가장 작은 스코빌 지수가 K값 미만 일 때마다 앞의 두 항목을 pop()하고 새 스코빌 지수를 push()해나가야하기 때문에 삽입/삭제 이후에도 정렬을 유지하는 Min Heap구조를 사용하면 유용하다.

Min Heap은 부모가 자식 노드보다 값이 항상 작은 완전 이진 트리 구조로, 작은 값이 우선순위에 오르는 기준을 가진 우선순위 큐이다.

Heap의 삽입/삭제는 O(log n)이 걸리고 이는 이진 트리 구조이기 때문에 트리 레벨 수에 따라 삽입/삭제 후에 정렬이 이뤄져야 하는 노드 수가 달라지기 때문이다.

 

문제의 제한 사항을 보면 scoville의 길이가 최대 1,000,000이 될 수 있기 때문에 scoville을 매번 sort하는 방식으로 음식을 섞으면 O(n^2 log n)의 시간 복잡도를 가지게 되므로 시간 초과가 날 수있다.

따라서 삽입/삭제 시마다 O(log n)이 소요되는 힙을 사용하면 O(n log n)으로 시간 초과가 나지 않고 문제를 풀 수 있다.

import heapq
def solution(scoville, K):
    answer = 0

    #scoville를 min heap 구조로 heapify -> O(n)
    heapq.heapify(scoville)

    while True:
	#1. 음식을 모두 섞은 스코빌이 K보다 작은 경우, -1 return
        if len(scoville) == 1:
            if scoville[0] < K: return -1
       
        #2. min heap의 root가 K보다 작은 경우, 스코빌이 가장 작은 두 음식을 섞는다.
        if scoville[0] < K:
	    #섞는 횟수 카운팅
            answer += 1
	    # 첫 heappop()으로 반환 가장 작은 스코빌이 반환되고 이를 두 번째 heappop()으로 반환된 스코빌의 2배 해 준 값과 더한다. -> T(2 log2 n) = O(log n)
	    # 음식을 섞은 후의 스코빌을 min heap에 push한다. -> O(log n)
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville)*2)

	#3. min heap의 root 스코빌이 K이상인 경우 모든 음식의 스코빌이 K이상이므로 return
        else: return answer
    return answer

#시간 복잡도 = O(n log n) 공간 복잡도 = O(n)