프로그래머스 - 더 맵게

문제

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

풀이

heap을 사용하여 문제에 접근하면 쉽게 풀 수 있다.
문제에서 요구하는 방법대로 접근하면

1. 최소 스코빌 두개를 문제에서 제시한 공식을 이용하여 힙 트리에 삽입, 그리고 1회 수행할 때 마다 카운터를 추가하거나, 횟수를 알아 볼 수 있는 방법을 이용한다. (삽입연산 : O(logN) / 힙 추출 : O(1))
2. 파이썬에서 제공하는 heapq는 트리 인덱스 0이 최대/최소값으로, 0번 값만 K와 비교하여 K보다 높으면 조건을 충족한다.

추가로 고려해야할 점?

위의 풀이대로 해당 문제를 풀다가 테스트 케이스 18번만 틀리는 상황이었는데,
음식을 섞지 않고 기존 스코빌 점수가 이미 K값을 넘을 때 상황을 고려해야한다. 이 때는 위의 풀이 방법을 적용하지 않고 바로 0을 출력하도록 해야한다

소스코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    if scoville[0] >= K:
        return answer
    while True:
        if len(scoville) == 1 or len(scoville) == 0:
            return -1
        food1 = heapq.heappop(scoville)
        food2 = heapq.heappop(scoville)
        new_food = food1 + (food2 * 2)
        answer += 1
        heapq.heappush(scoville,new_food)
        if scoville[0] >= K:
            return answer

전체적인 시간복잡도는 O(N)정도로 추측하고 있다.