문제 설명
매운 것을 좋아하는 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 합니다.
입출력 예
scoville K return
[1, 2, 3, 9, 10, 12] 7 2
풀이과정
먼저 했던 방법은 재귀함수를 사용한 해결이었다.
- 리스트를 K 이하인 요소만 남긴다.
- shake 함수에 위 리스트와 k, cnt를 넘겨준다
1 들어온 리스트 요소들이 k 보다 작은지 체크
2 sort 해서 arr[0] + arr[1]*2 로 섞어줌.
3 섞은 요소 + arr[2:]
4 cnt + 1
5 반복
def shake (arr,k,cnt) :
if len([a for a in arr if a < k]) == 0:
return cnt
cnt += 1
arr.sort()
shaked = [arr[0] + arr[1]*2] + arr[2:]
return shake (shaked,k,cnt)
def solution(scoville, K):
answer = 0
new_scoville = [i for i in scoville if i < K]
answer = shake(new_scoville, K,0)
return answer그러나 값은 잘 나왔지만 런타임 에러가 나고 효율성 문제의 경우 모두 틀리는...그런 결과가 나왔다..😢
그래서 조금 더 효율적인 자료형을 생각하다가 가장 맵지않은~ 두번째로 매운~ 이라는 문제의 문항을 보고 순서가 중요하고 sort 보다 빠르게 정렬할 수 있는 구조가 무엇일까? 생각하게 되었다.
그러다 우선순위 큐가 sort 라이브러리 보다 빠르다는 것을 수업 시간에 들은 기억이 났다.
바로 검색 시작...
c++과 비슷하게 우선순위 큐는 파이썬도 다행히 라이브러리로 제공을 해준다!! (heapq에 대한 자세한 내용)
heapq는 다른 언어의 모듈과는 다르게 고맙게도 push , pop을 하면 자동으로 정렬을 해주는 아주 아주 고마운 녀석이다 👍 (이름 답게 아주 힙한..녀석..🤘🖖)
그래서 알고리즘을 재정리 하자면
- 빈 리스트(heap)을 만들어준다.
- scoville를 우선순위 큐로 만들어 heap에 저장한다.
- heap의 가장 작은 값이 k보다 클때까지 반복
3-1. 힙의 가장 작은, 두번째로 작은 요소를 빼 섞어줌.
3-2. cnt +1
자동으로 정렬을 해주니 추가적인 코드를 쓰지않아서 아주 편하다 😁
import heapq
def solution(scoville, K):
p_qeue = []
cnt = 0
for num in scoville :
heapq.heappush(p_qeue,num)
while p_qeue[0] < K :
try:
heapq.heappush(p_qeue, heapq.heappop(p_qeue) + heapq.heappop(p_qeue) * 2)
except IndexError:
return -1
cnt += 1
return cnt
