[Python] 프로그래머스 더 맵게 풀이

문제 확인

프로그래머스

나의 풀이

• 가장 덜 매운 두 음식을 고르기 위한 방법으로 우선, 정렬을 생각해볼 수 있다. 
• 하지만 K는 10억이라 정렬의 횟수가 많아지기 때문에 시간 초과가 발생할 것이다.
• 따라서 항상 최소값을 보장할 수 있는, 최소 힙 자료구조를 활용한다.
  • 최소 힙을 이용할 경우, 각 push와 pop은 $\log N$의 시간 복잡도를 가지게 된다.

[자료구조] 힙(heap)이란 - Heee's Development Blog (gmlwjd9405.github.io)

# K가 10억 -> 반복 횟수가 매우 큼
# 100 만의 길이를 계속 정렬한다면 시간 초과가 발생!
from heapq import heappush, heappop, heapify

def solution(scoville, K):
    # 실행 횟수
    cnt = 0
    # 최소힙으로 변경
    heapify(scoville)
    while True:
        # 가장 맵지 않은
        s1 = heappop(scoville)
        # 가장 안 매운 음식이 K 넘으면, 나머지는 확인할 필요 X
        if s1 >= K:
            break
        # 두 번째로 맵지 않은
        if scoville:
            s2 = heappop(scoville)
        # 구성 못한 경우
        else:
            cnt = -1
            break
        # 섞기
        s = s1 + (s2 * 2)
        heappush(scoville, s)
        cnt += 1
    
    return cnt