[프로그래머스] LEVEL2 더 맵게 (Python)

[프로그래머스] LEVEL2 더 맵게

🧐 문제 설명

😍 나의 풀이

최소값과 그 다음 최소값을 이용하는 문제여서 힙정렬을 이용하기로 했다. 파이썬은 heapq 모듈(기본이 최소힙)을 제공하기 때문에 쉽게 힙을 만들 수 있다. 이 문제도 힙을 사용하는 방법만 알면 쉽게 문제를 풀 수 있는데 다음 조건은 생각해봐야하는 점이다.

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

예를 들어, scoville 리스트가 [0,0,0,0] 으로 아무리 힙을 이용한 계산과정을 반복해도 K를 넘을 수 없는 case 혹은 K값이 너무 크게 주어져서 계산을 계속 해도 K를 넘을 수 없는 case가 존재한다.

즉 이 문제는 힙에서 최소 원소를 두 개 빼서 연산 후 그 계산 값을 힙에 넣는 과정을 반복하다보면, 힙의 원소가 1개씩 계속 줄어드는 상황이 발생한다. 이 때, 힙이 더 이상 연산을 할 수 없는 원소 갯수가 되었을 때도 남아 있는 원소들이 모두 K를 넘지 않으면 -1을 return하면 된다.

위 문제에서는 heappop()을 2번 수행해야하는데 힙의 길이가 2보다 작게 되면 더 이상 연산을 수행할 수 없으므로 그때도 최솟값이 K를 못 넘는다면 -1을 반환하도록 했다.

import heapq

def solution(scoville, K):
    count = 0
    heapq.heapify(scoville) #리스트를 힙으로 변환
    
    while scoville[0] < K:          
        new = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        heapq.heappush(scoville, new)
        count +=1
        
        if scoville[0] < K and len(scoville) < 2 :
            return -1
        
    return count

👏 다른 사람의 풀이

대부분 heapq 모듈을 사용해서 풀어서 크게 다른 코드는 없지만, 위에서 말한 조건을 처리하는 과정에서 힙의 참조할 수 없는 인덱스에 대해서 try-except로 처리한 것이 깔끔해보여서 긁어왔다.

def solution(scoville, k):
    import heapq
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)

    mix_cnt = 0

    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        mix_cnt += 1

    return mix_cnt

🥇 Today I Learn

heapq module

파이썬에서 제공하는 힙큐 모듈, 일반적인 리스트를 최소 힙처럼 다룰 수 있음

힙에 원소 추가 : heappush(힙, 원소)

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
-----------------------
[1, 3, 7, 4]	# 결과

힙에 원소 삭제 : heappop(힙)

원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소(최솟값)를 삭제 후에 그 값을 리턴

print(heapq.heappop(heap))
print(heap)
--------------------------
1	
[3, 7, 4]	# 결과

힙의 최솟값 삭제없이 접근 : 힙[0]

print(heap[0])

기존 리스트를 힙으로 변환 : heapify(리스트)

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)
-------------------------
[1, 3, 5, 4, 8, 7]

[응용] K번째 최소값/최대값

K번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출

[응용] 최대 힙

heapq 모듈은 최소 힙(min heap)만 동작하기 때문에 최대 힙(max heap)으로 활용하려면 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용

따라서 최대 힙을 만들려면 각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제! 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값 이용

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
--------------------------------------------
8
7
5
4
3
1	#결과