알고리즘 - 프로그래머스(더 맵게)

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

프로그래머스

 

나의 답

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> p = new PriorityQueue<>();
        for(int s : scoville) p.add(s);
        int count = 0;
        while(p.peek()<K){
            if(p.size()==1){
                return count = -1;
            }
            int a = p.poll();
            int b = p.poll();
            int c = a+(b*2);
            p.add(c);
            count++;
        }
        answer = count;
        return answer;
    }
}

 

이번에 heap의 구조를 알아봤다.

 

자바로는 priorityQueue를 사용

 

- priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
- priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

하면서 엄청 신기했다. 

p.poll(), p.add()시에 가장 작은 값을 호출 가능하고, 호출 한 순간 정렬이 된다.

가장 낮은 수는 최 상단에 위치하게된다.

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

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리