프로그래머스 Lv2 힙 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 17분

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville:
        
        v1 = heapq.heappop(scoville)
        
        if v1<K:
            if len(scoville)==0:
                answer = -1
                break
            
            if scoville:
                v2 = heapq.heappop(scoville)
                heapq.heappush(scoville,v1+(v2)*2)
                answer += 1
        else:
            break
        
    return answer

음식의 스코빌 지수를 담은 배열 (scoville) 원하는 스코빌 지수(K)가
입력될 때, 모든 음식의 스코빌 지수를 원하는 스코빌 지수 이상으로 만드는 문제입니다.🐨🐨🐨

단, 특정 음식의 스코빌 지수가 원하는 스코빌 지수보다 낮을 때 '섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)' 공식으로 섞을 수 있는 조건입니다.

최소 스코빌 지수의 음식들부터 판별하여 조건에 따라 섞으면 되므로, 입력된 음식의 스코빌 지수들을 최소 힙 구조로 변환한 뒤 pop했을 때 K보다 작을 시 섞는 방식으로 구현하였습니다.

또한 모든 음식들의 스코빌지수를 K이상으로 만들 수 없을 때 -1을 반환해야하는 조건을 만족하기 위해, 최소 스코빌 지수인 모든 음식들을 섞어 남은 음식이 1개이고 K이상을 만족하지 못할때 -1을 반환하게 하였습니다.

[다른 사람의 풀이1]

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0

    while True:
        first = hq.heappop(scoville)

        if first >= K:
            break
        if len(scoville) == 0:
            return -1

        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

'나의 풀이'처럼 Python의 heapq 라이브러리를 활용하여 해결한 풀이입니다.

일부 케이스에서 더 빠른 처리를 위해

if first >= K:
	break

최소 힙 구조의 첫번째 요소가 K값을 만족하면 break하여 끝내는 조건을 걸어준 부분만 달랐습니다.

[다른 사람의 풀이2]

import heapq


def solution(scoville, k):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)

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

        return mix_cnt

마찬가지로 heapq 라이브러리를 통해 힙 구조를 구현한 방식입니다.🐑🐑🐑

코드 표현상 다른 점은 모든 음식을 섞어도 K 스코빌지수를 만들 수 없는 경우를 try-except 구문으로 표현한 점입니다.

감사합니다.