[Java] [더맵게] PriorityQueue

Priority Queue

• Heap 자료구조(Binary Tree) 를 통해 구현
• Queue 형태로 우선순위 정렬되며, 최대/최소값 탐색 가능
• Binary Tree 탐색으로 시간복잡도 logN 

■ 활용

## 오름차순 선언 ##
PriorityQueue<Integer> pq = new PriorityQueue<>(); 

## 내림차순 선언 ##
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); 

## 함수 ##
pq.add();      //추가
pq.offer();    //추가 or exception error

pq.peek()      //반환
pq.element()   //반환 or exception error

pq.poll()      //반환후제거 
pq.remove()    //제거 or exception error

pq.clear()     //비우기

 

■ 프로그래머스 - Heap - 더맵게

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;        
        
        // PriorityQueue 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>(); 
        
        // pq.add()
        for(int i=0; i<scoville.length; i++){
            pq.add(scoville[i]);
        }
        
        // pq.peek(), pq.poll(), pq.size(), pq.isEmprty()
        while(pq.size()>1){            
            int food = pq.poll() + (pq.poll() * 2);
            pq.add(food);
            answer++;            
            if(pq.peek()>=K) break;            
        }
        
        // 제약조건
        if(pq.size()==1 && pq.peek()<K) return -1;
        if(pq.size()==0) return -1;
        
        // 출력
        return answer;
    }
}