P42628. 이중우선순위큐

문제

제출 코드

• 사용 알고리즘 : 자료구조, 우선순위 큐

문제명 그대로, 큐에 삽입한 숫자를 크기순으로 정렬하여 최댓값과 최솟값을 꺼낼 수 있도록 구현하면 되는 문제이다.

보자마자 PriorityQueue의 Deque버전이 있다면 한번에 풀릴텐데..? 라고 생각해서 찾아봤으나 그런 자료구조는 아쉽게도 없었기에, 정렬기준이 다른 두가지 큐를 사용해서 풀었다.

이 풀이에서 핵심은, 두가지 큐의 정보를 어떻게 업데이트 해야할까였다.

최댓값을 삭제할 땐 내림차순으로 정렬된 PriorityQueue에서 값을 꺼내는데, 이렇게 꺼내진 값을 오름차순으로 정렬된 PriorityQueue에서도 삭제처리를 해야한다.

결국엔 Number라는 클래스를 따로 구현해서, 값을 삽입할 때 인덱스도 같이 넣어주며 개별 값들을 식별했다. 삭제 시 deleted에 삭제된 값임을 표시해주어, 다른 큐에서 값을 꺼낼 때 유효한 값인지 판별하도록 했다.

이번 풀이에서 오랜만에 써서 겨우 기억해 낸 Collections.reverseOrder().

이번처럼 우선순위 큐를 오름차순, 내림차순으로 모두 구현해야 할 때 유용하게 쓰인다.

Arrays.sort(정렬할 배열, Collections.reverseOrder());으로 내림차순 정렬할때도 쓸 수 있다.

import java.util.*;

class Solution {

    static class Number implements Comparable<Number>{
        int idx, value;
        Number(int idx, int value){
            this.idx = idx;
            this.value = value;
        }
        @Override
        public int compareTo(Number o){
            return this.value - o.value;
        }
    }

    public int[] solution(String[] operations) {

        PriorityQueue<Number> minQueue = new PriorityQueue<Number>();
        PriorityQueue<Number> maxQueue = new PriorityQueue<Number>(Collections.reverseOrder());

        int idx = 0;
        boolean[] deleted = new boolean[operations.length];

        for(String oper : operations){
            StringTokenizer st = new StringTokenizer(oper);

            if(st.nextToken().charAt(0)=='I'){ //삽입 연산
                int num = Integer.parseInt(st.nextToken());
                minQueue.add(new Number(idx, num));
                maxQueue.add(new Number(idx++, num));

            }else{ //삭제 연산
                if(st.nextToken().charAt(0)=='-'){ // 최솟값 삭제
                    while(!minQueue.isEmpty()){
                        Number now = minQueue.poll();
                        if(!deleted[now.idx]) {
                            deleted[now.idx] = true;
                            break;
                        }
                    }
                }else{ // 최댓값 삭제
                    while(!maxQueue.isEmpty()){
                        Number now = maxQueue.poll();
                        if(!deleted[now.idx]) {
                            deleted[now.idx] = true;
                            break;
                        }
                    }
                }
            }
        }

        int[] answer = new int[2];

        // 최댓값 출력
        while(!maxQueue.isEmpty()){
            Number now = maxQueue.poll();
            if(!deleted[now.idx]) {
                answer[0] = now.value;
                break;
            }
        }

        // 최솟값 출력
        while(!minQueue.isEmpty()){
            Number now = minQueue.poll();
            if(!deleted[now.idx]) {
                answer[1] = now.value;
                break;
            }
        }

        return answer;
    }
}