파이썬 / 프로그래머스 / 더 맵게

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

---

공식

 

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

 

---

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

- scoville의 길이는 1 이상 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

 

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

풀이

 

이번 구현은 자꾸 시간 초과나서... 다른 걸 보고 공부해보고 풀었다.

힙과 관련된 문제였고, 나는 이 부분들을 리스트만을 이용했다.

 

def solution(scoville, K):
    answer = 0
    while min(scoville) < K: #제일 작은 값이 K보다 작으면 무한 루프 돌게
        if(len(scoville)==1):
            return -1;
        answer = answer + 1
        sortedScoville = sorted(scoville)# 정렬
        temp = sortedScoville[0]+(2*sortedScoville[1]) # 스코빌 지수 구하기
        del sortedScoville[0]
        sortedScoville.insert(0,temp)
    
    return answer   

 

결과는 수정된 코드도 시간 초과^^

def solution(scoville, K):
    answer = 0
    min = 0
    #최소값 찾기
    for i in scoville :
        if min > i :
            min = i
    while min < K: #제일 작은 값이 K보다 작으면 무한 루프 돌게
        if(len(scoville)==1):
            return -1;
        answer = answer + 1
        
        for i in range(len(scoville)):
            for j in range(len(scoville)-1):
                if scoville[j] > scoville[j+1]:
                    temp = scoville[j]
                    scoville[j] = scoville[j+1]
                    scoville[j+1] = temp
                    
        temp1 = scoville[0]+(2*scoville[1]) # 스코빌 지수 구하기
        del scoville[0]
        scoville.insert(0,temp1)
    
    return answer   

 

다른 코드 찾아보니 heapq라는 파이썬의 내장 모듈을 이용했다.

코드는 이 블로그를 참조했다.

https://itholic.github.io/kata-more-spicy/

 

이 모듈은 이진 트리(binary tree)기반의 최소 힙(min heap) 자료구조를 제공한다.

heapq.heappush를 이용하여 우선 순위 큐 또는 힙을 쉽게 생성한다.

 

import heapq

def solution(scoville, K):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    answer = 0
    while heap[0] < K :
        try :
            heapq.heappush(heap,heapq.heappop(heap)+(heapq.heappop(heap)*2))
        except IndexError:
            return -1
        answer += 1
    
    return answer

추가적으로 인상깊었던 것은 try except문을 잘 사용한다는 점?

나같은 경우에는 배열의 길이로 판단했지만, try except문을 잘 활용한다면 저렇게 깔끔한 코드가 될 거 같다.