[Heap] 프로그래머스 level 2 더 맵게 java 풀이

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

프로그래머스

 

Heap 이란?

자료구조 중 하나로, 일반적으로 우선순위 큐(Priority Queue)를 구현하기 위해 사용되는 이진 트리 구조.

• 힙은 일반적으로 '최소 힙(Min Heap)' 또는 '최대 힙(Max Heap)' 두 가지 종류로 나뉨
• 최소 힙(Min Heap)에서는 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같다.
• 최대 힙(Max Heap)에서는 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같다.
• 새로운 요소를 힙에 삽입하면 힙 속성을 유지하기 위해 재배치(Heapify) 작업이 수행.
• 루트 노드를 삭제하면 힙의 마지막 노드를 루트로 이동하고 다시 힙 속성을 유지하기 위해 재배치 작업이 수행.

 

문제 접근

1. Heap에서 작은 두 값 Pop
2. 스코빌 지수 만들고 Push
3. target 스코빌 지수 이상일 때 까지 반복, 반복 횟수++
4. 못 만들면 -1 return, 만들면 count return

 

코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int value : scoville) {
            minHeap.add(value);
        }

        int cnt = 0;
        while (minHeap.peek() < K) {
            if (minHeap.size() == 1) {
                return -1;
            }
            int min1 = minHeap.poll();
            int min2 = minHeap.poll();
            int scovilleValue = calculateScoville(min1, min2);
            minHeap.add(scovilleValue);
            cnt++;
        }
        return cnt;
    }

    private int calculateScoville(int val1, int val2) {
        return val1 + (val2 * 2);
    }
}