[Level 2] 더 맵게(Python)

프로그래머스

문제

• scoville: Leo가 가진 음식의 스코빌 지수 배열(길이 2 이상 1,000,000)
  • scoville의 원소는 각각 0 이상 1,000,000이하

• K: 원하는 스코빌 지수(0 이상 1,000,000,000 이하)
  • 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 return

• 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

풀이 과정

풀이 시간: 15분

알고리즘: 힙

 

scoville의 길이가 최대 1,000,000이기 때문에 최대 O(NlogN)의 알고리즘으로 설계해야 된다.
매 번 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 섞은 후,

다시 scoville에 추가하고 정렬한다면 시간초과가 날 수 밖에 없음
→ 힙은 삭제 및 삽입 연산이 O(logN)이기 때문에 힙 자료구조를 사용해야 됨(삽입 후 정렬을 다시 해줄 필요가 없음)

 

시간 복잡도: O(NlogN)

1. 리스트(모든 음식)를 힙 자료구조로 변환(heapify): O(N)

2. 최악의 경우, 모든 음식을 섞어야 할 수도 있음(N-1)번: O(N)

3. 섞는 동안 발생하는 heappop, heappush: O(logN)

 

코드

from typing import List
import heapq

def solution(scoville: List, K: int) -> int:
    """
    scoville: Leo가 가진 음식의 스코빌 지수 배열
    K: 원하는 스코빌 지수
    """
    answer = 0 # 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수
    heapq.heapify(scoville) # 최소힙으로 변환
    while scoville[0] < K: # 가장 맵지 않은 음식이 K보다 작을 때
        answer += 1
        if len(scoville) >= 2: # 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 꺼내서 섞기
            first = heapq.heappop(scoville)
            second = heapq.heappop(scoville)
            heapq.heappush(scoville, first + second * 2)
        else: # 음식이 하나인데 K보다 작다면 모든 음식을 원하는 스코빌 지수로 만들 수 없음
            return -1
    return answer