99클럽 코테 스터디 10일차 TIL - [프로그래머스] 이중우선순위큐 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 이중우선순위큐 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/42628

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 이중 우선순위 큐가 할 연산 String[] operations (1 ≤ operations.length ≤ 1,000,000)
출력 : 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]

가능한 시간복잡도

O(n)

알고리즘 선택

우선순위 큐

📌 코드 설계하기

1. 최소값을 유지하는 우선순위 큐 minHeap, 최대값을 유지하는 역순으로 정렬된 우선순위 큐 maxHeap을 생성한다.
2. 각 연산을 순회하며 I로 시작하는 경우, 값을 두 개의 큐에 삽입한다.
3. D로 시작하는 경우, 1일 때는 최대값을 maxHeap에서 제거하고, 해당 값을 minHeap에서도 제거한다.
4. -1일 때는 최소값을 minHeap에서 제거하고, 해당 값을 maxHeap에서도 제거한다.
5. 모든 연산이 끝난 후, minHeap이 비어있다면 [0, 0]을 반환하고, 그렇지 않으면 최대값과 최소값을 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

offer(E e) : 지정된 요소를 우선순위 큐에 삽입한다.
poll() : 우선순위 큐의 헤드를 제거하고 반환한다.
peek() : 우선순위 큐의 헤드를 제거하지 않고 반환한다.

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

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

            if (command.equals("I")) {
                minHeap.offer(value);
                maxHeap.offer(value);
            } else if (command.equals("D")) {
                if (value == 1) {
                    if (!maxHeap.isEmpty()) {
                        int max = maxHeap.poll();
                        minHeap.remove(max);
                    }
                } else if (value == -1) {
                    if (!minHeap.isEmpty()) {
                        int min = minHeap.poll();
                        maxHeap.remove(min);
                    }
                }
            }
        }

        if (minHeap.isEmpty()) {
            return new int[] {0, 0};
        } else {
            return new int[] {maxHeap.peek(), minHeap.peek()};
        }
    }
}