[프로그래머스] 42628. 이중우선순위큐

문제 링크

[프로그래머스] 42628. 이중우선순위큐

풀이 과정

하나의 우선 순위 큐를 사용하면 사용된 정렬 방법에 따라 최대 혹은 최소 값은 삭제할 수 있으나, 나머지 하나를 어떻게 처리할 지가 관건이었습니다.

각각 오름차순, 내림차순으로 정렬되는 두 개의 우선순위 큐 를 사용하게 된다면, 한쪽에서 지운 값을 다른 쪽에서도 지울 수 있게 됩니다.

위와 같은 우선순위 큐가 주어진다면, 빨간 네모 친 값을 아래와 같은 코드로 지울 수 있습니다.

int min = ascending.poll();
descending.remove(min);

ArrayDeque 자료구조는 PriorityQueue 와는 다르게 생성자에 comparator 를 사용하지 못합니다. 또한 Collections.sort 메소드도 사용하지 못하니, 문제와 같이 동작하기 위해서는 삽입 후 List로의 변환 및 정렬 작업이 필요할 것 같습니다.

코드

import java.util.PriorityQueue;

public class Main {
    public static int[] solution(String[] operations) {
        int[] answer = new int[2];

        PriorityQueue<Integer> ascending = new PriorityQueue<>((o1, o2) -> o1 - o2);
        PriorityQueue<Integer> descending = new PriorityQueue<>((o1, o2) -> o2 - o1);

        for (String s : operations) {
            String[] ss = s.split(" ");
            if (ss[0].equals("I")) {
                ascending.add(Integer.parseInt(ss[1]));
                descending.add(Integer.parseInt(ss[1]));
            } else if (ss[0].equals("D") && !ascending.isEmpty()) {
                if (Integer.parseInt(ss[1]) == 1) {
                    int max = descending.poll();
                    ascending.remove(max);
                } else if (Integer.parseInt(ss[1]) == -1) {
                    int min = ascending.poll();
                    descending.remove(min);
                }
            }
        }

        if (!ascending.isEmpty()) {
            answer[0] = descending.peek();
            answer[1] = ascending.peek();
        }

        return answer;
    }

    public static void main(String[] args) {
        String[] operations = {"I 16", "D 1"};

        solution(operations);
    }
}