뚝딱뚝딱

문제 자체가 힙을 구현하는 카테고리에 있는 걸 보고 접근한 거라, priorityqueue로 풀 수 있다는 걸 알고 풀어서 쉽게 풀어버린 케이스이다. 그래도 오랜만에 heap을 다루는 것이기도 하고, java에 있는 pq를 쓰는 건 처음이라 메소드도 익힐 수 있었다.

💡 Min Heap (PriorityQueue)

Heap?
- 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조.
- 힙에서는 중복된 값을 허용.
- max heap은 가장 큰 값이 부모노드에, min heap은 가장 작은 값이 부모노드에 있다.
- 부모노드는 자식노드보다 크거나 같고(max heap), 작거나 같아야(min heap) 한다.

- 힙은 배열을 통해 구현할 수 있다.
- 구현을 쉽게 하기 위해 0번 인덱스는 사용하지 않는다.
- 루트 노드가 1번 인덱스이다.
- 왼쪽 자식 노드 인덱스 : (부모노드 인덱스)*2
- 오른쪽 자식 노드 인덱스 : (부모노드 인덱스)*2+1
- 부모 노드 인덱스 : (자식노드 인덱스)/2

자바에서 힙은 java.util에 있는 PriorityQueue를 사용할 수 있고, 기본적으로 min heap을 구현한다.

💡 java.util.PriorityQueue

- 기본적으로 mean heap을 구현한다.
- 요소 삽입 : offer()
- 가장 작은 요소 반환 및 삭제 : poll()
- 가장 작은 요소 반환 : peek()
- 힙의 크기 반환 : size()

이 정도로 정리해 두면 문제는 충분히 풀 수 있다.

문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.


Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.


모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식의 스코빌 지수가 K이상이 된다는 것은, min heap에서 가장 우선 순위에 있는 노드의 값이 K이상인 것과 같고, 그렇게 되면 그 아래 모든 노드는 K이상이 되기 때문에, min heap을 이용해서 아주 쉽게 이 문제를 해결할 수 있다.

알고리즘은 다음과 같다.

1. PriorityQueue 객체를 Integer 타입으로 생성한다.
2. 스코빌 배열에 있는 모든 값을 우선순위 큐에 삽입한다.
3. while문을 통해 다음의 조건을 만족하는 경우에만 반복실행한다
   "우선순위 큐의 가장 작은 값=가장 먼저 나오는 값이 K보다 작고, 우선순위 큐에 있는 요소가 2개이상인 경우"
   다음을 실행한다
   우선순위 큐에서 가장 작은 값 두개 꺼내고 위의 식을 통해 섞은 음식의 스코빌 지수를 구한 후 이를 다시 큐에 삽입한다. 그리고 answer 값을 1 올린다.
   위 과정을 조건을 만족할 경우에 반복한다
4. 위 과정을 마치고 나면 큐는 스코빌 지수가 모두 K이상이거나, 큐에 있는 요소가 2개 미만인 상태일 수 있다.
5. 전자의 경우라면 answer를 그대로 반환하면 되고, 후자의 경우라면 모든 음식을 섞어도 K이상이 안된다는 것이므로 문제에서 주어진 조건에 따라 -1을 반환하면 된다.

전체 코드는 아래와 같다.

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int item : scoville){
            pq.offer(item);
        }
        
        while(pq.peek()<K && pq.size()>=2){
            int temp1 = pq.poll();
            int temp2 = pq.poll();
            pq.offer(temp1+(temp2*2));
            answer++;
        }
        
        if(pq.size()==1 && pq.peek()<K) return -1;
        
        return answer;
    }
}

*** while문을 실행하고 나면 어차피 pq.peek()<K라는 것은 pq.size()==1인 것과 동시에 일어나기 때문에, 마지막 if문에서는 pq.peek()K만 만족하면 -1을 반환하도록 코드를 줄여도 된다.