👨‍💻 문제

---

✍️ 풀이

🔀 2개의 우선순위 큐

오름차순으로 정렬되는 우선순위 큐와
내림차순으로 정렬되는 우선순위 큐

총 2개의 우선순위 큐를 활용하여 구현하였다.

단순히 해당 구조로만 구현한다면
하나의 큐에서 요소를 삭제해도 다른 큐에는 해당 요소가 남아있게 된다.

이것을 해결하기 위해 숫자를 wrapping하는 클래스를 하나 만든다.

❔️ 삭제된 숫자

숫자에 삭제되었는가? 라는 변수를 추가된 클래스를 작성한다.

이를 활용하면 다른 큐에서 삭제된 요소가 존재하는지 확인할 수 있다.

    private static class Number implements Comparable<Number>{
        int value;
        boolean deleted;

        public Number(int value) {
            this.value = value;
        }

        public void delete() {
            deleted = true;
        }

        public boolean isDeleted() {
            return deleted;
        }

        ...
    }

큐에서 값을 뺄 때,

현재 빼려는 요소가 이미 사라진 요소라면 큐에서 빼고 다음 값을 뺀다.

                        // 이미 다른 큐에서 삭제된 요소 삭제
                        pollAlreadyDeletedNumbers(pqToPoll);
                        if (!pqToPoll.isEmpty()) {
                            pqToPoll.poll().delete();
                        }
                        
    ...
                        
    private static void pollAlreadyDeletedNumbers(PriorityQueue<Number> pq) {
        while (!pq.isEmpty() && pq.peek().isDeleted()) {
            pq.poll();
        }
    }

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static class Number implements Comparable<Number>{
        int value;
        boolean deleted;

        public Number(int value) {
            this.value = value;
        }

        public void delete() {
            deleted = true;
        }

        public boolean isDeleted() {
            return deleted;
        }

        public int getValue() {
            return value;
        }

        public int compareTo(Number number) {
//            return value - number.value;  <--  Integer.MIN_VALUE 아래로 값이 내려갈 수 있음
            return Integer.compare(value, number.value);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t=0; t<T; t++) {
            int n = Integer.parseInt(br.readLine());
            PriorityQueue<Number> pq = new PriorityQueue<>();
            PriorityQueue<Number> reversePq = new PriorityQueue<>(Collections.reverseOrder());

            for (int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                char operation = st.nextToken().charAt(0);
                int number = Integer.parseInt(st.nextToken());

                switch (operation) {
                    case 'I' :
                        // 같은 객체를 양쪽에 집어넣는다
                        Number numberObj = new Number(number);
                        pq.add(numberObj);
                        reversePq.add(numberObj);
                        break;
                    case 'D' :
                        PriorityQueue<Number> pqToPoll = (number == 1) ? reversePq : pq;

                        // 이미 다른 큐에서 삭제된 요소 삭제
                        pollAlreadyDeletedNumbers(pqToPoll);
                        if (!pqToPoll.isEmpty()) {
                            pqToPoll.poll().delete();
                        }
                        break;
                }
            }

            // 남은 쓰레기 요소 정리
            pollAlreadyDeletedNumbers(pq);
            pollAlreadyDeletedNumbers(reversePq);

            sb.append((pq.isEmpty() && reversePq.isEmpty()) ? "EMPTY\n" : String.format("%d %d\n", reversePq.poll().getValue(), pq.poll().getValue()));
        }

        System.out.print(sb);
    }

    private static void pollAlreadyDeletedNumbers(PriorityQueue<Number> pq) {
        while (!pq.isEmpty() && pq.peek().isDeleted()) {
            pq.poll();
        }
    }

}