[프로그래머스] 이중우선순위큐 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42628#

프로그래머스

 

---

 

문제 개요

이중 우선순위 큐는 일반적인 우선순위 큐의 기능을 확장하여 최댓값과 최솟값을 동시에 관리할 수 있는 자료구조입니다. 이 문제에서 주어진 연산에는 다음과 같은 기능이 있습니다.

• I 숫자: 숫자를 큐에 삽입합니다.
• D 1: 큐에서 최댓값을 삭제합니다.
• D -1: 큐에서 최솟값을 삭제합니다.

이 연산을 처리한 후 큐가 비어 있으면 [0, 0], 비어 있지 않으면 [최댓값, 최솟값]을 반환해야 합니다.

해결 방법

1. 우선순위 큐 활용
   자바의 PriorityQueue를 사용하여 이중 우선순위 큐를 구현합니다. 이 자료구조는 기본적으로 최솟값을 기준으로 정렬됩니다.
2. 최대/최소값 삭제 처리
   • D -1: 기본적으로 최솟값을 제거하는 poll() 메서드를 사용하여 PriorityQueue에서 최솟값을 제거합니다.
   • D 1: 최댓값을 제거하려면 모든 요소를 새로운 큐에 옮겨 넣어 poll()을 남기고 비우는 방식으로 최댓값을 제거합니다.
3. 최댓값 및 최솟값 반환
   연산을 모두 수행한 후, 큐가 비어 있으면 [0, 0]을 반환하고, 그렇지 않으면 큐에서 최솟값과 최댓값을 반환합니다.

 

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 연산 수행
        for (int i = 0; i < operations.length; i++) {
            String[] arr = operations[i].split(" ");
            if (arr[0].equals("I")) {
                // 숫자를 큐에 삽입
                pq.add(Integer.parseInt(arr[1]));
            } else {
                if (!pq.isEmpty()) {
                    if (arr[1].equals("-1")) {
                        // 최솟값 제거
                        pq.poll();
                    } else {
                        // 최댓값 제거
                        PriorityQueue<Integer> bucket = new PriorityQueue<>();
                        int len = pq.size();
                        for (int j = 0; j < len - 1; j++) {
                            bucket.add(pq.poll());
                        }
                        pq = bucket;
                    }
                }
            }
        }

        // 결과 계산
        if (pq.size() == 1) { //하나일 경우 최솟값 최댓값 일치           
            int n = pq.poll();
            return new int[]{n, n};
        }
        if (pq.size() > 1) {
            answer[1] = pq.poll();  // 최솟값
        }
        while (pq.size() > 0) {
            answer[0] = pq.poll();  // 최댓값
        }

        // 결과 정리
        if (answer[1] > answer[0]) {
            int tmp = answer[1];
            answer[1] = answer[0];
            answer[0] = tmp;
        }
        return answer;
    }
}