프로그래머스 level 2 더 맵게, heap

걸린 시간 : 1시간

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

입출력 예

사고과정

가장 작은 수를 a에 저장하고 배열을 내림차순으로 정렬한 뒤에 맨 마지막 요소를 제거한다. 그 다음 작은 수 b도 같은 방식으로 구하고 a+b*2 를 리스트에 더해준다. 이걸 scoville 리스트의 가장 작은 수가 K보다 커지기 전까지 반복하고 카운트를 출력한다.

def solution(scoville, K):
    count = 0
    while min(scoville) < K: 
        a = min(scoville)
        scoville = sorted(scoville, reverse=True)
        scoville.pop()

        b = min(scoville)
        scoville = sorted(scoville, reverse=True)
        scoville.pop()
        
        scoville.append(a+2*b)
        count += 1

    return count

답은 잘 나오는데 1,3,8,14번이 런타임 에러로 실패했고 효율성 테스트를 다 실패했다.

최대 scoville 길이만큼 반복하는 코드의 시간 복잡도는 O(N * Nlog(N))입니다. 왜냐하면 매 반복시 정렬을 해주어야하기 때문입니다. 힙의 저장과 삭제 연산은 O(log(N))의 시간 복잡도를 가집니다. 출처 : 구르미의 개발 이야기

힙이란?

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

파이썬 힙 자료구조

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.

heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

힙 함수 활용하기

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

출처: 아기여우의 자기계발로그

제출 코드

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

    while scoville[0] < K:
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        
        heapq.heappush(scoville, heapq.heappop(scoville)+heapq.heappop(scoville) * 2)
        cnt += 1
    
    return cnt

주요 포인트 및 생각해볼 점

레벨1을 하면서 시간을 너무 많이 보낸 것 같다. 이번 주말에는 레벨2를 되도록 많이 다루면서 새로운 개념에 대해서 알아봐야겠다.