프로그래머스 - [LEVEL 2] 더 맵게

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

---

문제 설명

- scoville: 음식의 스코빌 지수가 담긴 리스트

- k: 스코빌 지수

조건: scoville 리스트에 모든 값이 k이상이 되게 해야합니다.

위 조건을 만족하게 하기위해 섞는 과정을 거칩니다. 몇번 섞어야하는지 리턴하면 되는 문제입니다. (조건을 만족 못할 시 -1 리턴)

 

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

 

ex)

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

---

풀이

heapq를 활용한 문제입니다.

heapq: 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조

출처: www.daleseo.com/python-heapq/

 

매번 sort를 하고 조건을 검사하기에는 상당한 오버헤드가 발생합니다.

heapq자료구조를 활용하여 O(logN)으로 push와 pop을 하고 정렬된 채로 있습니다. 이로써 시간초과 문제를 해결할 수 있습니다.

 

처음에 sort를 진행하고, while문에서 섞는 과정을 하며 조건검사를 진행해 줍니다. 코드를 보시면 이해됩니다!

 

코드

import heapq

def solution(scoville, K):
    
    answer = 0
    scoville.sort()
    
    while True:
        # heapq를 사용하면 맨 앞에 변수가 제일 작은 변수가 됨
        if scoville[0] >= K:
            return answer
        
        # 길이가 1이 되면 K 이상으로 만들 수 없음
        elif len(scoville) == 1:
            return -1
        
        # 섞기: 가장 낮은 + (두번째 낮은 * 2)
        else:
            first = heapq.heappop(scoville)
            second = heapq.heappop(scoville)
            new_scovil = first + (second * 2)
            
            heapq.heappush(scoville, new_scovil)
            answer += 1
        
    return answer