[자료구조] 우선순위 큐 Priority Queue (프로그래머스 더 맵게 java 풀이)

1. 우선순위 큐(Queue)란?

일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조.

이런 큐의 특성과 달리 우선순위 큐는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다.

 

 

2. 우선순위 큐 function

E peek() : 큐의 처음에 있는 원소를 삭제하지 않고 가져온다. 큐가 비어있으면 null을 반환

boolean offer(E e) :원소를 추가할 때 큐의 용량을 넘어서면 false를 반환한다.

E poll() : 큐의 처음에 있는 원소를 가져온다. 큐에 원소가 없으면 null을 반환한다.

E remove() : 큐의 처음에 있는 원소를 제거한다. 큐에 원소가 없으면 예외가 발생한다.

 

 

3. 우선순위 큐가 사용되는 코드 예제

프로그래머스 더 맵게 java 풀이

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> h = new PriorityQueue();
        
        for(int i=0; i<scoville.length; i++)
            h.offer(scoville[i]);
            
        while(h.peek()<=K){
            if(h.size()==1){
                return -1;
            }
            int s1 = h.poll();
            int s2 = h.poll();
        
            int r = s1 + s2*2;
        
        h.offer(r);
        answer ++;
        }
        return answer;
    }
}

 

 

+ Queue에 값 추가, add와 offer의 차이점

q.add(x);

해당 큐 맨 뒤에 값 삽입

값 추가 성공 시 true 반환

큐가 꽉 찬 경우 IllegalStateException 에러 발생

 

q.offer(x);

해당 큐 맨 뒤에 값 삽입

값 추가 성공 시 true 반환

값 추가 실패 시 false 반환