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

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        for(String s : operations) {
            int N = Integer.parseInt(s.substring(2));
            if(s.charAt(0) == 'I') {
                min.add(N);
                max.add(N);
            }
            else {
                if(N == -1 && !min.isEmpty()) {
                    min.poll();
                    max.clear();
                    max.addAll(min);
                }
                else if(N == 1 && !max.isEmpty()) {
                    max.poll();
                    min.clear();
                    min.addAll(max);
                }
            }
        }
        if(!min.isEmpty()) {
            answer[0] = max.peek();
            answer[1] = min.peek();
        }
        return answer;
    }
}

2. 설명

자바의 자료구조인 PriorityQueue를 이용하여 최소 힙과 최대 힙을 기반으로 최솟값을 제거하면 최대 힙의 정보를 지우고 최소힙 내용으로 덮어쓰며 최댓값을 제거할 때는 반대로 한다면 마치 두 개의 우선순위 큐를 사용하여 최솟값과 최댓값을 지운 것처럼 되어 쉽게 해결이 가능하다.

3. 정리

1. 최대 값과 최소 값을 지우는 문제에서 우선순위 큐를 1개가 아닌 2개를 활용하면 쉽게 구현 가능하다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges