[프로그래머스] 더 맵게

원본 링크

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

Intro

이번 문제에선 힙(Heap)이라는 자료구조를 활용해서 문제를 풀게 된다.
자료구조 관련 강의를 들으면 Tree를 배우면서 후반부에 배우게 되는 구조이다.
뭔가 내용도 복잡해서 잘 안 쓸 것 같아 보이나, 지금과 같이 최대/최소 연산을 주로 하는 경우 효율을 내기 좋다.

문제 설명

매운 것을 좋아하는 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회입니다.

나만의 풀이

본 문제를 풀기 위해서는 힙(Heap)이라는 자료구조를 알아야 한다.

잠시 과거 강의 요점노트를 인용하면, Heap은 이진 검색 트리(BST)의 불균형 분배를 해결하기 위해 만들어진 자료구조라 되어있다.
크게 구조는 Max Heap 과 Min Heap 이 있으며, Max힙은 트리 구조에서 무조건 부모가 자식보다 큰 값을 지니고, Min힙은 무조건 부모가 자식보다 작은 값을 지닌다는 것이 특징이다.
따라서 크기 순서를 고려해서 연산을 수행할 때 쓰기 좋은 자료구조라 할 수 있다.
어쨌든 이진 트리이므로, 검색은 O(logn) 정도이며, 최대/최소값 파악은 O(1)이 된다.

자료구조 관련 개념은 해당 내용까지만 작성하고, 이제 파이썬에서 heap을 쓰는 법을 알아보도록 하자.
파이썬에선 별도로 heapq 라이브러리를 활용해서 힙을 구현할 수 있다.
크게 3가지 종류의 연산이 있다.

• heapq.heapify(리스트): 리스트를 힙으로 정렬
• heapq.heappush(힙, 데이터): 힙에다가 데이터를 넣음
• heapq.heappop(힙):힙에서 가장 첫 원소를 뽑아냄

단, 여기서 지원하는 힙은 Min heap구조이다.
만일 Max heap을 쓰고 싶으면 마이너스 부호를 붙여서 push & pop을 해야 한다.

아무튼, 이제 문제에서 주어진 solution()함수에 맞춰서 내용을 작성해보자.
먼저, scoville 리스트를 heapq.heapify를 써서 heap으로 만들어준다.
이후 scoville의 맨 첫 번째 원소가 k값 보다 크거나 같을 때까지 while문을 돌면서 연산을 수행하자.

만일 scoville의 원소가 1개 이하면 더 이상 합칠 수 없으니 -1을 리턴해주면 된다.
그 외의 경우는 2개의 원소를 heapq.heappop()해서 앞선 문제의 조건대로 계산 후, 다시 heap.heappush()를 해주면 된다.
어차피 힙 내부에서 push할 때 정렬은 알아서 해 준다.
이때, 연산 횟수도 하나씩 증가해주면 되겠다.

최종적으로 다음과 같이 코드를 짤 수 있다.

import heapq  # heap queue 사용

def solution(scoville, k):
    heapq.heapify(scoville)  # heapify는 한 번만.

    cnt = 0

    while scoville[0] < k:  # 맨 처음 원소 기준.
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(scoville) + (heapq.heappop(scoville) * 2))  # 바로 계산
            cnt += 1
        else:
            return -1  # 불가능

    return cnt  # 가능한 경우

마치면서

파이썬 자체에서 이미 라이브러리를 지원하기 때문에 쉽게 힙을 구현하고 쓸 수 있었다.
사실 힙 구조는 그 자체로 쓰기 보다는 우선순위 큐를 만들 때 주로 이용하곤 한다.
따라서 우선순위 큐에서 특히 많이 사용되는 구조이기도 하다.

나중에 우선순위 큐를 사용하는 문제가 나오면 조금 더 상세히 다뤄보려 한다.