문제설명
매운 것을 좋아하는 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 합니다.
풀이
python은 내가 제일 처음 배운 프로그래밍 언어지만, 뭐 그것도 학부 때 일이고...
선택지가 [c++, JAVA, python3] 3개밖에 없어서 그나마 잘 아는 걸로 했지만 평소 사용하는 언어가 아니라 좀 헤맸다.
처음에는 sort()로 풀려하다가 heap을 쓰지않으면 통과를 못하는 것 같길래 노선을 바꿨다.
heapq 모듈에 관한 기본 사항들을 정리해보고 넘어가보자 한다.
- heap에 관한 간단 영상
https://youtu.be/AjFlp951nz0
heapq
이진트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 기본적으로 제공하는 모듈이다.
heapq를 import해서 파이썬의 리스트를 최소 힙처럼 다루게 만들어준다.
heap = []
- 원소 추가
heapq.heappush(heap, 추가하려는 value)
- 원소 삭제
heapq.heappop(heap)
재밌는 건 단순 삭제가 아니라 최소값을 리턴하면서 삭제한다.
그래서 아래와 같이 삭제하지 않으면서 최소값을 얻을 수 있다.
- 최소값 얻기
heap[0]
- 리스트를 힙으로 변환
list = [1,2,3,4]
heapq.heapify(list)
기본적인 함수들은 요런 느낌.
이 문제를 풀려면 배열에서 가장 작은 수와 두번째로 작은 수를 아는 게 필수이기 때문에 처음엔 당연히 sort()를 이용했지만 그럼 효율성에서 통과를 못한다.
그러니 일단 scoville를 heapify()를 이용해 힙으로 변환시켰다.
위에서 말했다시피 heappop()은 최소값을 리턴하면서 값을 삭제시키기 때문에 스코빌 지수를 얻는 데 사용했다. 어차피 K 이상의 스코빌 지수가 나오지 않으면 최소값을 얻은 후 해당 값을 삭제해야하는데 그 과정을 줄여준다.
그 후 heappush로 값을 넣고 해당 과정을 반복할 때마다 결과값이 +1씩 증가하도록 했다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return한다는 조건이 있기 때문에 배열이 줄어들다가 하나 남았을 때 해당 값이 K보다 작으면 -1을 return하도록 했다.
- 참고 : while문에 배열 길이 조건 안 넣으면 정확도 테스트 1,3,8에서 런타임 에러 뜨면서 통과 안 된다..
제출 코드
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while scoville[0] < K and len(scoville) > 1:
scoville_value = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
heapq.heappush(scoville, scoville_value)
answer += 1
if len(scoville) == 1 and scoville[0] < K:
answer = -1
return answer