문제
매운 것을 좋아하는 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 합니다.
문제를 보고 든 생각
정렬 문제인 것 같기도 하고 그리디 알고리즘 문제인 것 같기도 했다.
나의 아이디어
문제를 읽고 생각을 하다보니 무조건 정렬이 필요한 문제였고 요소를 빼고 다시 집어 넣는 과정이 필요했다.
그리고 요소를 집어 넣을 때도 정렬을 무조건 필요로 했다.
이럴 거면 힙을 쓰는 게 괜찮겠다고 생각했다.
마침 리스트에서 빠지는 요소도 항상 가장 작은 요소와 그 다음으로 작은 요소 이렇게 두 개이기 때문에 최소힙을 쓰면 알맞을 것 같다고 생각했다.
위에서 언급한 정렬, 삭제, 삽입, 그리고 다시 정렬의 과정만 처리해준다면 나머지는 간단했다.
섞는 횟수를 세어주고 스코빌 지수를 계산해주기만 하면 되기 때문이었다.
결과
import heapq
def solution(scoville, K):
count = 0
def mixing(val1, val2):
mixed = val1 + (val2 * 2)
return mixed
while True:
heapq.heapify(scoville)
if len(scoville) == 1 and scoville[0] < K or K != 0 and sum(scoville) == 0:
count = -1
break
if any(K > value for value in scoville):
mixed = mixing(heapq.heappop(scoville), heapq.heappop(scoville))
heapq.heappush(scoville, mixed)
count += 1
else:
break
return count
정확성 케이스는 모두 정답 처리 받았지만, 효율성 케이스에서는 모두 시간 초과를 받았다.
효율성은 생각하지 않고 적긴 했다.
코드를 짜면서도 k보다 작은 스코빌 지수를 찾는 과정이 O(n)이라서 코드가 총 O(n^2)이 되기 때문이었다.
이 과정만 바꿔주면 충분히 효율성 테스트까지 통과할 수 있을 텐데
도저히 생각이 나지 않았다.
개선
import heapq
answer = 0
heapq.heapify(scoville)
while True:
val1 = heapq.heappop(scoville)
if val1 >= k:
break
elif len(scoville) == 0:
answer = -1
break
val2 = heapq.heappop(scoville)
mixed = val1 + val2 * 2
heapq.heappush(scoville, mixed)
answer += 1충분히 k보다 낮은 스코빌 지수를 찾는 과정에서의 시간복잡도를 줄일 수 있었지만 생각해내지 못했다.
상당히 단순하기 때문에 왜 그걸 놓쳤을까라는 생각이 들었다.
핵심은 문제에 있었다.
리스트 안에 스코빌 지수보다 낮은 요소가 있는지 확인하기 위해서는 항상 첫 번째 인덱스의 스코빌 지수만 확인하면 된다.
첫 번째 인덱스의 수가 k보다 크다면 리스트의 나머지 요소 모두 k보다 큰 것이고 아니면 작은 것이다.
왜냐?
최소힙을 사용하고 있기 때문이다.
whlie문의 루프를 끊어주는 조건문 2개는 아래와 같다.
1. 리스트의 맨 앞 요소가 k와 같거나 k보다 크면 나머지 요소들도 모두 k와 같거나 크기 때문에 답을 출력하기 위해 루프를 종료한다.
2. 리스트의 맨 앞 요소를 pop한 후 min에 저장하고 나서 (1)번 if문의 조건을 충족하지 못했다면 k와 같거나 k보다 큰 수를 만들 수 없다는 말과 같기 때문에 -1을 반환한다.
느낀 점
1. 알아가는 것이 몇 가지 있다. 힙에서 요소를 빼거나 힙에 요소를 더해줄 때마다 heapify를 해주지 않아도 된다는 사실을 알았다.
2. 힙 문제를 많이 풀어보지 않았는데 오늘을 통해 문제를 풀 때 힙 사용을 고려해도 좋은 상황이 언제인지 맛을 본 것 같다.
