[programmers] 이중우선순위큐 - Java

이중우선순위큐

문제 설명

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

• operations의 원소는 큐가 수행할 연산을 나타냅니다.
• 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.

• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

입출력 예 설명

• 16과 -5643을 삽입합니다.

• 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.

• 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.

• 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.

• 123을 삽입합니다.

• 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.

• 45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.

• 642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.

• 333을 삽입합니다.

solution.java

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
         
        for(String s: operations){
            int num = Integer.parseInt(s.substring(2));
            if(s.startsWith("I")){
                pq.add(num);
            }else if(s.startsWith("D 1")){
                deleteMax(pq);
            }else{
                pq.poll();
            }
        }
        
        if(pq.size()==0){
            return new int[2];
        }
        else{
            return getMaxAndMin(pq);
        }
    }
    
    private PriorityQueue<Integer> deleteMax(PriorityQueue<Integer> pq){
        
        if(pq.size()==0)
            return pq;
        
        ArrayList<Integer> tempList = new ArrayList<>();
        
        while (pq.peek() != null) {
            tempList.add(pq.poll());
        }
        
        Collections.sort(tempList);
        
        tempList.remove(tempList.size()-1);
        
        for (int num : tempList) {
            pq.offer(num);
        }
        
        return pq;
    }
    
    private int[] getMaxAndMin(PriorityQueue<Integer> pq){
        ArrayList<Integer> tempList = new ArrayList<>();
        
        while (pq.peek() != null) {
            tempList.add(pq.poll());
        }
        
        Collections.sort(tempList);
        
        int min = tempList.get(0);
        int max = tempList.get(tempList.size() - 1);
        
        return new int[] {max, min};
    }
}

핵심 키워드

• 우선순위 큐에서 최솟값을 제거하기 위해 PriorityQueue 로 선언된 큐에서 poll() 을 한다.

• 우선순위 큐에서 최댓값을 제거하기 위해 PriorityQueue 의 값을 ArrayList로 복사하고 정렬해서 최댓값을 제거한다.
• 최댓값을 제거한 ArrayList 의 값을 PriorityQueue 로 복사해서 리턴한다.

결론!