[프로그래머스 / 자바 / Lv.3] 42628 이중우선순위큐

문제

풀이

 

이중우선순위큐를 구현하는 문제로, 주어진 명령어들을 처리하여 최종적으로 큐의 최댓값과 최솟값을 반환하는 것이다.

1. 두 개의 우선순위 큐 생성 (최소힙, 최대힙)

- 최대힙 정렬은 `Collections.reverseOrder()`로 큐 역순 정렬하여 최대힙을 만든다.

2. 명령어 규칙대로 처리

- I : min, max 두 큐에 모두 add 연산을 수행

- D 1 : 최댓값 삭제

- D -1 : 최솟값 삭제

3. 큐가 비어있으면 [0, 0] 반환하고, 비어있지 않으면 max.peek()으로 최댓값, min.peek()로 최솟값 반환함.

class Solution{
        public int[] solution(String[] operations) {
            PriorityQueue<Integer> min = new PriorityQueue<>();
            PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
            StringTokenizer st;

            for (int i=0; i<operations.length; i++){
                st = new StringTokenizer(operations[i]);
                char op = st.nextToken().charAt(0);
                int num = Integer.parseInt(st.nextToken());

                switch(op) {
                    case 'I':
                        min.add(num);
                        max.add(num);
                        break;
                    case 'D':
                        if(max.isEmpty()) break;
                        if(num == 1) {
                            int del = max.poll();
                            min.remove(del);
                        }
                        if(num == -1) {
                            int del = min.poll();
                            max.remove(del);
                        }
                }
            }

            if(max.isEmpty()) {
                return new int[] {0, 0};
            }
            return new int[] {max.peek(), min.peek()};
        }
    }