[알고리즘] 우선순위큐(Priority Queue)

[우선순위 큐(Priority Queue) - JAVA] 

 

 

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

 

일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조이다. 이런 큐의 특성과 달리 우선순위 큐는

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

 

 

2. 우선순위 큐 function

 

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

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

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

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

 

 

3. 우선순위 큐를 이용한 자바 프로그램

 

[프로그래머스 - 더 맵게]

 

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42626

 

-해답

import java.util.PriorityQueue;
 
class Solution {
   public int solution(int[] scoville, int K) {
               PriorityQueue<Integer> que=new PriorityQueue<Integer>();
            
            //큐에 배열 넣어주기
            for(int num:scoville){
                que.add(num);
            }
       
            //섞은 횟수 저장할 변수
            int count=0;
 
            while(que.peek()<K&&!que.isEmpty()) {//peek()은 꺼내지 않고 값만 확인
                int lessSpicy=que.poll();//poll()은 우선순위가 젤 우선인 값을 꺼냄
                
                if(!que.isEmpty()){
                    int secondLessSpicy=que.poll();
                    que.add(lessSpicy+secondLessSpicy*2);
                    count++;
                }else{
                    return -1;
                }
            }
       
            return count;
   }
}