[Programmers] 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스 - 더 맵게

힙을 이용하는 문제였다.

자료구조 ‘힙(heap)’이란?
완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이며,
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

힙은 파이썬에서 모듈로 구현되어 있는데, 이 모듈을 사용하여 문제를 풀었다.

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    answer = 0

    while True:
        min_food1 = heapq.heappop(scoville)
        if min_food1 >= K:
            return answer
        elif len(scoville) == 0:
            return -1
        min_food2 = heapq.heappop(scoville)

        temp = min_food1 + (min_food2 * 2)
        heapq.heappush(scoville,temp)
        answer += 1

1. 리스트를 heap 구조로 만들어주는 heapify를 이용하여 scoville을 힙으로 만들어준다.
2. 모든 음식의 스코빌지수가 K 이상일 때까지 반복하라고 했으므로 while 문을 사용함
3. 힙에서 가장 작은 값은 가장 앞에 있는 값이므로 heappop을 이용하여 가장 작은 값을 pop 해준다.
   3-1. 이때 가장 작은 값인 min_food1이 K보다 클 경우엔 scoville 내의 모든 값이 다 큰 것이므로 0을 리턴해준다.
   3-2. 모든 음식의 스코빌지수를 K 이상으로 만들 수 없을 경우에는 -1을 리턴해준다.
4. 예제에서 나왔던 것처럼 두 번째로 작은 값을 heappop을 이용하여 pop 해준다.
5. 덜 매운 값 + 두 번째로 덜 매운 값*2한 값을 temp에 저장하고, 그 값을 scoville에 넣어준다.

2~5까지 이 과정을 반복한다.

tmi)

알고리즘을 풀면서 발견한 나의 단점 : 자꾸 문제 명시와는 다르게 다른 쪽으로 생각하려는 경향이 있음.
이번 문제도 문제에 나온 그대로를 구현하면 됐지만, 왜 두 번째 값을 이용하지? 마지막 값을 이용하면 안 되나?라는 생각으로 오랜 시간을 헤맸다.
다음 문제부턴 있는 그대로를 구현해보고, 답이 안 나오면 위처럼 생각하는 걸루...