[알고리즘 문제 풀이] - 더 맵게 (프로그래머스)

오늘은 프로그래머스에서 더 맵게 라는 문제를 풀어 보았습니다.

 

<문제 설명>

매운 것을 좋아하는 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 합니다.

input은 scoville이라는 음식들의 스코빌 지수가 담겨져 있는 리스트와 K가 주어집니다.

 

목적은 이 scoville 이라는 리스트안에 답긴 모든 스코빌 지수들의 값을

 

K보다 높게 만드는 겁니다. K보다 작은 스코빌 지수를 가진 음식이 있다면 

 

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

이 공식을 이용해서 두 음식을 섞어 스코빌 지수를 높여야 합니다.

 

저는 이 공식을 보자마자 이 문제는 스코빌 지수들을 가장 낮은 숫자부터 오름차순으로 정렬해야 된다는

 

생각이 먼저 들었네요. 처음에는 그냥 리스트를 정렬 해서 쓰려고 했습니다.

 

하지만 두 음식을 섞어서 새로운 스코빌 지수를 리스트 안에 넣을때마다 또 새로 정렬을 해야 하고

 

시간을 많이 잡아먹어서 결국 효율성 테스트에서 시간 초과가 나왔습니다... ㅜ

 

그래서 새로운 아이템을 넣을 때마다 정렬이 되는 힙을 사용하였습니다.

 

heappush와 heappop은 O(logN)의 시간복잡도를 가지고 있기 때문에 

 

 O(NlogN)의 시간복잡도인 sort()보다 훨씬 더 효율적이었습니다.

 

문제의 알고리즘은 정말 간단합니다.

 

가장 작은 스코빌 지수부터 빼내서 K와 비교를 합니다.

 

가장 작은 스코빌 지수가 K보다 크다면 힙 안에 있는 모든 스코빌 지수들은 K보다 크다는 뜻이겠죠?

 

그럼 거기서 loop은 종료

 

K보다 작다면 두번째 작은 스코빌 지수까지 빼내고 주어진 공식을 이용해서 

 

두 음식을 섞은 스코빌 지수를 heap 안에 넣어 줍니다.

 

heappush의 경우 아이템을 집어 넣음과 동시에 정렬까지 되니

 

이런 유형의 문제에는 정말 유용한 자료구조 입니다.

 

import heapq as hq

def solution(scoville, K):
    count = 0
    hq.heapify(scoville)
    while True:
        smallest = hq.heappop(scoville)	 #가장 낮은 스코빌 지수
        if smallest < K:	#가장 낮은 스코빌 지수가 K보다 낮을때
            if scoville:
                second_smallest = hq.heappop(scoville)
                hq.heappush(scoville, smallest + second_smallest*2)
                count += 1
            else:	 #모든 음식의 스코빌 지수를 K 이상으로 만들수 없을때
                count = -1
                break
        else:
            break
    return count

그렇다면 채점해본 결과는?

 

사실 정확성 쪽으로 어려울만한 edge case는 없는 문제 같아요.

 

하지만 효율성 쪽으로 상당히  난이도가 있는 문제 였습니다.

 

확실히 자료구조를 배울땐 관련된 문제를 풀어보는게 도움이 많이 되는것 같습니다.

 

결국 자료구조들을 어떤 문제에 어떻게 적용할 것인지가 중요한것 같네요.