[프로그래머스 LV2] 더 맵게 - 파이썬

문제링크

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

프로그래머스

1. 문제 간단히하기

가장 낮은 스코빌 두개 => 섞은 스코빌 = 가장낮은 + (두번째낮은 * 2)

모든음식의 스코빌이 k이상이 될때까지 섞는다(최소의 값이 k이상일때까지)

초기문제풀이

def solution(scoville, K):
    answer = 0
    while True:
        cur_min = min(scoville)
        if cur_min >= K:
            break
        if len(scoville) == 1:
            return -1
        scoville.remove(cur_min)
        cur_min2 = min(scoville)
        scoville.remove(cur_min2)
        answer += 1
        mix = cur_min + (cur_min2 * 2)
        scoville.append(mix)
    return answer

현재의 최소값이 k이상이면 break해주고 되지않으면 break해주는 형식으로 문제를 풀이하였다.

당연히 시간초과!

heapq를 사용하여서 시간복잡도를 줄이는 방법을 알게 되었다.

최소힙

힙은 최소힙과 최대 힙이 있다.

최소 힙은 루트 노드에 최소값이 있는 것이고, 최대 힙은 루트 노드에 최대값이 있는 것이다.

파이썬의 heapq에서는 최소힙만 지원된다.

 

힙의 루트 노드는 0번 인덱스이다. 최소값이 0번 인덱스에 존재하는 것이다.

즉

처음 heappop() =>  현재 힙의 가장 최소값

두번째 heappop() => 두번째 최소값

 

루트가 k이상이면 모든 스코빌이 k이상이고

힙의 길이가 1개이면 더이상 k를 만들 수 없게 break를 해주면 될것이고

더 남아있다면 mix = 최소값 + (두번째최소값 * 2)를 해줘서 heap에 넣어주면된다.

실행코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # List를 heapq으로 만들어준다
    while scoville[0] < K: # 가장 작은 수가 기준보다 낮다면 계속
        if len(scoville) > 1:
            answer += 1
            first = heapq.heappop(scoville)
            second = heapq.heappop(scoville)
            heapq.heappush(scoville, first + second * 2)
        else:
            return -1
    
    return answer