[프로그래머스/Level2/파이썬3(python3)] 더 맵게

[프로그래머스/Level2/파이썬3(python3)] 더 맵게

문제

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

입출력 예 설명

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
    heapify(scoville)
    while scoville[0] < K and 1 < len(scoville):
        first = heappop(scoville)
        second = heappop(scoville)
        new = first + (second * 2)
        heappush(scoville, new)
        answer += 1
    return answer if scoville[0] >= K else -1

설명

다른 lvl2문제와 달리 생각보다 꽤나 간단했던 문제. 처음 만들었던 코드에는 몇몇 테스트케이스에서 런타임 오류(보통 에러)가 떠서 무슨 문제가 있을까 여러 케이스들을 테스트해봤는데 아니나 다를까 heappop하는 과정에서 다음 원소가 없을 때 (원소가 하나밖에 안남았을 때) second에서 불러올 요소가 없어서 깨져버리는 것이었다. 그것만 while 조건문에 하나 추가해줘서 간단하게 해결했다. 알고리즘 문제가 요즘 진짜 안풀려서 우울했는데 쉬우면서 자신감을 심어주는 문제였다.
 만약에 힙에 대해서 모른다면 https://www.fun-coding.org/Chapter11-heap.html 이곳을 참고해보는 걸 추천한다. 간단하게 설명하자면 heap은 최솟값과 최대값을 찾는 데 특화된 자료구조로서 이진탐색트리와 비슷한 모양을 가진 친구이다. 최솟값과 최대값을 찾는 데 보통의 list라면 O(n)의 시간복잡도를 갖고 있지만 heap을 사용하면 파이썬의 경우 list 자료형의 맨 앞에 위치시켜주기 때문에 O(1)의 시간복잡도를 갖는다는 장점이 있다. 이런 부분을 이용해 푸는 문제였다.