[Algorithm] 힙 우선순위큐 [Heap Priority Queue] (더 맵게)

문제 ]

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

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

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 합니다.

입력

scovile = [1,2,3,9,10,12]

K = 7

출력

return 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회입니다. Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

제출 1 ] 

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int result = 0;
        if(K==0) return 0;
        Arrays.sort(scoville);
        for(int i=0;i<scoville.length;i++){
            System.out.println(Arrays.toString(scoville));
            if(scoville[i]==0) return -1;
            if(scoville[i]<K){
                result = scoville[i]+(scoville[i+1]*2);
                if(result > scoville[i+2]) {
                    scoville[i+1]=scoville[i+2];
                    scoville[i+2]=result;    
                }
                answer++;
            } else {
                break;
            }
        }
        System.out.println(answer);
        return answer;
    }
}

몇 몇 테스트에서 타임아웃과 효율성테스트 실패.

결국 힙을 써야될 것같은데 자바의 Priority queue자료형쓰라는 문제였다.

[ Priority queue ]

큐의 구조를 가지면서 우선순위가 높은 엘리먼트가 먼저 poll되는 자료구조이다. 우선순위는 최대힙(내림차순)과 최소힙(오름차순)이 있으며 힙영역 메모리를 사용한다.

이진트리로 되어있으면 최대힙이면 root노드에 가장 큰 값, 

최소힙이면 root노드에 가장 작은 값이 들어간다.

기본적으로 import java.util.PriorityQueue; 를 임포트하고

PriorityQueue<제네릭> pq = new PriorityQueue<>(); 변수를 선언하여 사용한다. 

큐에 값을 추가하는 함수는

• pq.add() / pq.offer()

큐에 값을 삭제하는 함수

• pq.poll() // 첫번째 값(루트노드)을 반환하고 제거 비어있다면 null
• pq.remove() // 첫번째 값 제거
• pq.clear() // 우선순위 큐 초기화

출력 함수

• pq.peek() // 우선순위 큐 첫번째 값 출력
• pq.size() // number of elements present in the PriorityQueue

제출 2 ] 

import java.util.PriorityQueue;

class Solution {

public int solution(int[] scoville, int K) {

            PriorityQueue<Integer> pq = new PriorityQueue<>();

    int answer = 0;

        

            for (int i=0; i < scoville.length; i++){

                pq.add(scoville[i]);

            }

            while(pq.peek() < K){

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

                int a = pq.poll();

        int b = pq.poll();

        pq.add(a + 2 * b);

        answer++;

            }

        return answer;

}

}

우선순위 큐 참조 : 

https://coding-factory.tistory.com/603