💡 문제

더 맵게

• 유형 힙(Heap)

• 문제 설명

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

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

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

• 제한 조건
  • scoville의 길이는 2 이상 1,000,000 이하입니다.
  • K는 0 이상 1,000,000,000 이하입니다.
  • scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

• 입력
  • ex1) [1, 2, 3, 9, 10, 12], 7

• 출력
  • ex1) 2

• 참고
  • [kata][python] 프로그래머스 - 더 맵게 | 코딩장이
  • Python - 데크(deque) 언제, 왜 사용해야 하는가?
  • [Python] 더 맵게

✍🏻 풀이

TRY 1

# TRY 1) list 이용 : 정확성 통과, 효율성 미통과

def solution(S, K):
    S = sorted(S)
    cnt = 0
    for i in S:
        if i < K:
            S.append(S[0]+S[1]*2)
            S.sort()
            S = S[2:]
            cnt += 1
        if S[0] > K:
            break
        if (len(S) == 1) and S[0] < K:
            return -1
    return cnt

SOL 1

# SOL 1-1) 힙(heap) 자료구조 이용, try / except IndexError 이용
# 힙을 사용하는 이유 : 일반적인 리스트와 달리 push(), pop() 이후 자동 정렬

import heapq

def solution(S, K):
    heap = []
    for i in S:
        heapq.heappush(heap, i)

    cnt = 0
    while heap[0] < K:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap) * 2)
        except IndexError:
            return -1
        cnt += 1
    return cnt

# SOL 1-2) 힙(heap) 자료구조 이용

import heapq

def solution(S, K):
    heap = []
    for i in S:
        heapq.heappush(heap, i)

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

SOL 2

# SOL 2) 데크(deque) 자료구조 이용

from collections import deque

def solution(S, K):
    answer = 0 
    mix = deque()
    S.sort()
    sco = deque(i for i in S)
    
    while (sco and sco[0] < K) or (mix and mix[0] < K):
        answer += 1
        if len(sco) + len(mix) <= 1:
            return -1
        
        food = [0]*2
        for a in range(2):
            if sco and mix:
                if sco[0] < mix[0]:
                    food[a] = sco.popleft()
                else:
                    food[a] = mix.popleft()
            elif sco:
                food[a] = sco.popleft()
            else:
                food[a] = mix.popleft()
            
        mix.append(food[0]+food[1]*2)
        
    return answer

🌵 정리

깃헙에서 전체 코드 확인하기