[프로그래머스/Python] 더 맵게 - Level2

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

코딩테스트 연습 - 더 맵게

처음에 짠 코드를 까먹고 저장을 안해서 날려먹었지만... 일단 설명을 해보자면 scoville의 길이가 2이상일 때까지만 while문을 돌면서 최소값이 K이상이면 break를 하고 그렇지 않으면 "최소값1 + 최소값*2"를 계산하여 힙에 넣어주었습니다. 이렇게 코드를 짰더니 정확성 테스트에서 몇 개가 실패가 떴습니다.....ㅜ 질문하기에서 찾아보니 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1을 리턴해야한다는 것을 알았습니다!  근데 이 조건을 추가해줬는데도 테스트에 통과하지 못했습니다..... 그래서 다시 질문하기에서 나와 같은 케이스가 있는지 확인해보았습니다

 

 

 

이런 답변을 발견하고 while문을 위처럼 바꿨더니 테스트가 통과되었습니다! 이것이 바로 완성된 코드입니다.

 

import heapq

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

    # 최소값이 K 이하인 경우 음식 조합하기
    while scoville[0] < K:
        # 모든 스코빌 지수를 K이상으로 만들 수 없는 경우
        if len(scoville) == 1: 
            return -1
        
        # 스코빌 계산
        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville) 
        heapq.heappush(scoville, min1 + (min2 * 2))
        answer += 1
    
    return answer

이 문제는 힙 문제이기 때문에 힙큐(heapq)를 사용했습니다. heapq.heapify(scoville) 하여 리스트를 힙으로 바꾸어 주었습니다. 최소값이 K일 경우 스코빌을 계속 계산할 수 있도록 while문을 작성했습니다. 모든 스코빌 지수를 K이상으로 만들 수 없는 경우의 조건을 추가하여 return -1을 해주었습니다. 힙에서 최소값 두 개를 가져와 조합한 값을 다시 힙에 넣어주었다. answer에 +1도 해주었습니다.

 

- 배운 점 -

힙(Heap)

힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 합니다. 힙은 최소힙과 최대힙이 있습니다. 최소힙은 부모 노드가 자식 노드보다 작은 경우이고 최대힙은 부모 노드가 자식 노드보다 큰 경우입니다. 대소관계는 부모와 자식 간에만 성립되고 형제노드 사이에는 대소관계가 성립되지 않습니다.

 

 

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공합니다. 기본적으로 최소힙의 형태로 정렬됩니다. heapq는 내장모듈이라서 별도의 설치없이 import만 하면 사용할 수 있습니다. 다음은 heapq의 함수들입니다.

 

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

다음 예시를 보면 heapq를 사용하는 방법을 쉽게 알 수 있을 것입니다.

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap) # 출력: [10, 50, 20]

heapq.heappop()
print(heap) # 출력: [20, 50]

heap2 = [100 ,20, 70] # 리스트
heapq.heapify(heap2)
print(heap2) # 출력: [20, 100, 70]