[코딩테스트] Java 이중 우선순위 큐

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

최댓값과 최솟값을 효율적으로 관리 및 구하기 위해 최소 힙과 최대 힙을 두개 선언하고 연산에 맞게 관리합니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> min = new PriorityQueue<>();
        
        for (String operation : operations) {
            String[] split = operation.split(" ");
            String command = split[0];
            int number = Integer.parseInt(split[1]);

            switch (command) {
                case "I":
                    min.add(number);
                    max.add(number);
                    break;
                case "D":
                    if (number == 1 && !max.isEmpty()) {
                        int maxNum = max.poll();
                        min.remove(maxNum);
                    } else if (number == -1 && !min.isEmpty()) {
                        int minNum = min.poll();
                        max.remove(minNum);
                    }
                    break;
            }
        }
        
        int[] answer = {0, 0};
        if (!min.isEmpty() && !max.isEmpty()) {
            answer[0] = max.poll();
            answer[1] = min.poll();
        }
        
        return answer;
    }
}

코드 설명

• PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
  PriorityQueue<Integer> min = new PriorityQueue<>();
  최대 힙 max와 최소 힙 min을 초기화합니다. 이는 최소 값 및 최대 값을 빠르게 가져오거나 삭제하기 위해 사용됩니다.

• for (String operation : operations)
  operations 배열의 각 명령어를 순차적으로 탐색합니다. 각 명령어는 삽입 또는 삭제 작업을 나타냅니다.
  • String[] split = operation.split(" ");
    명령어를 공백으로 나누어 split 배열에 저장합니다. 첫 번째 요소는 명령어(I 또는 D), 두 번째 요소는 숫자를 나타냅니다.
  • String command = split[0];
    명령어(I 또는 D)를 command에 저장합니다.
  • int number = Integer.parseInt(split[1]);
    명령어의 숫자 값을 정수로 변환하여 number에 저장합니다.
  • switch (command)
    명령어(command)에 따라 조건문을 통해 동작을 결정합니다.
    • case "I":
      number를 min과 max 두 큐 모두에 추가합니다.
    • case "D":
      • if (number == 1 && !max.isEmpty())
        number가 1이면 최대값 삭제 명령어입니다. max에서 최대값을 poll()로 제거하고, min에서도 동일한 값을 remove()로 삭제합니다.
      • else if (number == -1 && !min.isEmpty())
        number가 -1이면 최소값 삭제 명령어입니다. min에서 최소값을 poll()로 제거하고, max에서도 동일한 값을 remove()로 삭제합니다.
  • int[] answer = {0, 0};
    • 결과를 담을 배열 answer를 선언하고 초기화합니다.
  • if (!min.isEmpty() && !max.isEmpty())
    • min과 max가 모두 비어 있지 않으면, answer[0]에 max의 최대값, answer[1]에 min의 최소값을 할당합니다.