Table of contents

프로그래머스 이중우선순위큐

명령어 수신 탑(높이)
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.

위와 같은 연산을 수행할 수 있는 이중 우선순위 큐가 있고, 연산 목록 operations가 주어졌을 때, 연산을 모두 수행한 후 남아있는 요소 중에서 최댓값과 최솟값을 찾는 문제이다.

풀이

두개의 우선순위큐를 사용해서 해결했다. 다른 사람들의 풀이도 대부분 비슷한 방식이었다.

@Test
public void test() {
    assertThat(solution(new String[]{"I 16", "D 1"}))
        .isEqualTo(new int[]{0, 0});
    assertThat(solution(new String[]{"I 7", "I 5", "I -5", "D -1"}))
        .isEqualTo(new int[]{7, 5});
}

public int[] solution(String[] operations) {
    Queue<Integer> queue = new PriorityQueue();
    Queue<Integer> reverseQueue = new PriorityQueue(Comparator.reverseOrder());

    for (String operation : operations) {
        String[] split = operation.split(" ");
        String oper = split[0];
        int value = Integer.parseInt(split[1]);

        if (oper.equals("I")) {
            queue.add(value);
            reverseQueue.add(value);
        } else if (value == 1){
            queue.remove(reverseQueue.poll());
        } else {
            reverseQueue.remove(queue.poll());
        }
    }

    return new int[] {
        reverseQueue.isEmpty() ? 0 : reverseQueue.poll(),
        queue.isEmpty() ? 0 : queue.poll(),
    };
}

데이터를 추가하는 연산의 경우 최대힙과 최소힙에 모두 넣는다. 최댓값을 삭제하는 연산의 경우 최대힙에서 노드를 꺼낸 뒤 최소힙에서 해당 노드를 찾아서 삭제한다. 최솟값의 경우는 최소값에서 노드를 꺼내 최대힙에서 삭제하면 된다.

남아있는 요소 중 [최댓값, 최솟값] 을 구하기 위해, 최댓값은 최대힙에서, 최솟값은 최소힙에서 각각 노드를 꺼내면 된다.