[코딩테스트 JAVA] 더 맵게 - 힙(Heap) , 우선순위 큐(PriorityQueue)

문제 설명
매운 것을 좋아하는 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인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

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

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

---

자료구조 ‘힙(heap)’이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
  • 💡 완전 이진 트리(Complete Binary Tree)란?
  • 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

힙(heap)의 종류

• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)
• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) <= key(자식 노드)

우선순위 큐는 지금까지 설명한 힙을 이용하여 만든 자료구조이다. 
일반적인 큐는 FIFO, 즉 먼저들어온 것이 먼저 나간다는 원칙을 가진 자료구조 이지만, 
우선순위 큐는 들어온 순서와는 상관없이, 우선순위가 가장 크거나 작은 자료가 가장 먼저 나간다. 
따라서 힙을 이용하여 가장 크거나 작은 자료를 O(1)시간만에 찾아서 내보낼 수 있으므로 Heap을 쓰는 것이 적합하다.

<출처 >

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

[자료구조] 힙(heap)이란 - Heee's Development Blog

https://velog.io/@gnwjd309/data-structure-heap

[자료구조] 힙(Heap) 이해하기

https://currygamedev.tistory.com/20#%F0%9F%94%BB%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90(Priority-Queue)

[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)

 

 

---

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 낮은 수가 우선
        
        for(int x : scoville){
            pq.offer(x);
        }
        
        int firstVal = 0;
        int secondVal = 0;
        
        while(pq.peek() < K){
            
            if(pq.size() < 2){
                return -1;
            }
            
            firstVal = pq.poll();
            secondVal = pq.poll();
            
            pq.offer(firstVal + (secondVal*2));
            answer++;
        }
        
        
        return answer;
    }
}

---

1.  우선순위 큐로 스코빌 지수 배열을 낮은 수부터 정리한다.

PriorityQueue<Integer> pq = new PriorityQueue<>(); // 낮은 수가 우선
        
for(int x : scoville){
    pq.offer(x);
}

 

2. 제일 낮은 수가 우선순위 큐에서 먼저 오게 되는데, 이 값이 K값보다 작을때 까지만 반복한다. 

 while(pq.peek() < K){
    ...
}

 

3. 다만, 첫번째 값과 두번째 값으로 계산해야 하므로 큐에 2개 이상 남아있을 때만 반복해야 오류가 안생긴다.

if(pq.size() < 2){
    return -1;
}

 

4. poll() 을 사용하면 첫번째 값을 꺼내오면서 변수에 저장할 수 있다. 

firstVal = pq.poll();
secondVal = pq.poll();

 

5. 큐에 계산한 값을 넣어준 다음, 섞은 횟수를 1 더해준다. 

pq.offer(firstVal + (secondVal*2));
answer++;