[프로그래머스 Lv.2] 더 맵게 (Heap)

1. 문제 설명

2. 제한 사항

3. 입출력 예

4. 문제 풀이

1) 문제 풀이 접근

• 배열을 오름차순 정렬해서 가장 작은 수가 K보다 작으면 가장 작은 수와 두 번째로 작은 수를 연산해서 새로운 수를 만듦
• 연산에 사용된 두개의 수를 제외하고 새로운 수가 추가된 배열을 다시 오름차순 정렬해서 앞선 과정을 반복하도록 코드를 구현함
• 하지만 삽입과 삭제, 그리고 정렬을 반복 하는 과정에서 시간이 많이 소요됨
• 최악의 경우 : 수가 하나 남을 때까지 섞어야 하는 경우 (n - 1회)
• 각 단계(섞는 일)에서 요구되는 계산량 : 정렬된 리스트에 순서 맞추어 원소 삽입 => O(n)
• 전체 문제 풀이의 복잡도 : O(n^2)
• 복잡도가 지나치게 높음

2) 성능 향상

• 최소/최대 원소를 빠르게 꺼낼 수 있는 방법을 찾아야 함
• 배열을 heap으로 만들면 root에 있는 값이 최소/최대 원소가 됨
• 최소/최대 원소를 상수 시간에 확인할 수 있음
• root에 있는 원소가 K보다 작으면 가장 작은 원소 두 개를 꺼내 연산한 후에 연산 결과 값을 삽입
• 삽입과 삭제 시간 복잡도 => O(logN)

3) heapq()

• heapq()로 생성한 비어있는 heap에 scoville 배열에 있는 값을 차례대로 heappush() 하면서 원래의 위치를 찾아가도록 구현

import heapq

def solution(scoville, K):
    answer = 0
    # 리스트를 heap으로 만듦
    heap = []
    for s in scoville:
        heapq.heappush(heap, s)
    while True:
    	# 모든 음식의 스코빌 지수가 K 이상이면 종료
        if heap[0] >= K:
            break
        # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 종료
        elif len(heap) == 1 and heap[0] < K:
            answer = -1
            break
        else:
        	# 스코빌 지수가 가장 낮은 두 개의 음식을 섞어 새로운 음식을 만듦
            a = heapq.heappop(heap)
            b = heapq.heappop(heap)
            heapq.heappush(heap, a + b * 2)
            answer += 1 # 섞은 횟수 증가
    return answer

4) heapq.heapify()

• heapify() : 배열의 원소들이 힙 구조에 맞게 재배치 => O(NlogN)
• heapq()와 heapify() 모두 heap을 만드는 것은 동일하나 배열 scoville을 바로 heap으로 바꾸는 해당 문제에서는 heapify()을 사용하는 것이 편리

import heapq

def solution(scoville, K):
    answer = 0
    # 리스트 scoville로부터 min heap 구성
    heapq.heapify(scoville) 
    while True:
      min1 = heapq.heappop(scoville) # min heap에서 최소값 삭제(반환)
      if min1 >= K:
        break
      elif len(scoville) == 0:
        answer = -1
        break
      min2 = heapq.heappop(scoville)
      heapq.heappush(scoville, min1 + min2 * 2) # min heap에 원소 삽입
      answer += 1
    return answer

• 전체 알고리즘의 시간 복잡도 : O(NlogN)