이번 문제는 제 맘 속의 제한 시간 45분 내 풀이하는데 실패했습니당 ㅠ. 어디까지 생각하고 결론을 도출하는데 까지만 정리하고 차후 풀이를 보고 이해한 뒤 정리하겠습니당.

문제

설명

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

접근

1차

힙Heap으로 분류되는 문제였습니당. 힙Heap이라는 개념을 숙지하지 못한 탓에 당연한 것을 먼저 살펴보았고 아래까지 결론을 도출했습니당.

1. 스코빌 배열은 항상 오름차순 정렬되어야 합니다.
2. K 이상인 스코빌은 이미 조건을 충족합니다. 따라서 무시해도 됩니다.
3. 남아 있는 음식들을 모두 섞어서 K를 넘어야 한다
4. 섞어서 K를 넘은 것은 빼도 된다

여기까지 생각을 하고, 스코빌을 오름차순으로 정렬하고 K이상인 원소는 필터링을 하면 초기에 $n\log n + n$ = O($n\log n$)을 투자하고, 처리량을 줄여 퍼포먼스에 이점이 있을 거라고 생각했습니당.

하지만, 필터링 안된 원소들 섞어 최종적으로 하나가 남을 때 조건을 만족하지 못하면, 조건 충족으로 인한 필터링된 원소들을 섞으면 되서 1번 전제가 잘못되었음을 깨달았어용...

3번도 마찬가지로 빼지 않고 남은 원소들과 섞어서 조건을 충족할 수 있기 때문에 1, 3번은 잘못된 사실이라는 것을 깨달았습니당

잘못된 사실이 참일지라도 섞을 때마다 정렬을 수행해야 하기 때문에 $n\log n * \frac{n}{2}$ = O($n^{2}\log n$)의 퍼포먼스를 나타내어 시간 초과가 뜰 것으로 예상하였습니당...

2차

python에서 제공하는 heapq 모듈을 사용했습니당. 이렇게 하면 list를 힙heap처럼 다룰 수 있다고 하여, 제 풀이에 고대로 적용하면 되지 않을까?!라고 생각하고 풀어보았습니당.

import heapq
from collections import deque

def solution(scoville, K):
	filtered_scoville = list(filter(lambda x: x < K, scoville))
	heapq.heapify(filtered_scoville)

	mixable = len(scoville) != len(filtered_scoville)

	answer = 0

	while len(filtered_scoville) >= 2:
		food1 =	heapq.heappop(filtered_scoville)
		food2 =	heapq.heappop(filtered_scoville)

		mixed = food1 + (food2) * 2
		answer += 1

		heapq.heappush(filtered_scoville, mixed)
	
	last_food = filtered_scoville[0]
	if last_food >= K:
		return answer
	
	if mixable:
		return answer + 1

	return -1


if __name__ == '__main__':
	print(solution([1, 2, 3, 9, 10, 12], 7))
	print(solution([1, 100], 2))

근데 결과는 '맵네요' ㅠ

아직 무언가가 남은 것 같습니당... 오늘은 힙heap에 대한 개념까지 정리하고 이만 마쳐야할 것 같습니당 ㅠ

3차(풀이 완료)

여기서 하나의 예외를 처리하지 못했습니당!

섞는 과정에서 모든 요리가 K 스코빌 지수를 만족하는 경우

그리하여, 도중에 이에 대한 예외 처리를 하면 정답이 완성됩니당!

import heapq
from collections import deque

def solution(scoville, K):
	filtered_scoville = list(filter(lambda x: x < K, sorted(scoville)))
	heapq.heapify(filtered_scoville)

	mixable = len(scoville) != len(filtered_scoville)

	answer = 0

	while len(filtered_scoville) >= 2:
		food1 =	heapq.heappop(filtered_scoville)
		food2 =	heapq.heappop(filtered_scoville)

		mixed = food1 + (food2) * 2
		answer += 1

		heapq.heappush(filtered_scoville, mixed)

		if filtered_scoville[0] >= K:	# 바로 요기!
			return answer
				
	last_food = filtered_scoville[0]
	if last_food >= K:
		return answer
	
	if mixable:
		return answer + 1

	return -1


if __name__ == '__main__':
	print(solution([1, 2, 3, 9, 10, 12], 7))
	print(solution([100, 1], 2))
	print(solution([1] * 1000000, 2))

Github : 더 맵게