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

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {};
        PriorityQueue<Integer> minq = new PriorityQueue<>();
        PriorityQueue<Integer> maxq = new PriorityQueue<>(Collections.reverseOrder());
        int len = 0;
        for(String s: operations){
            String[] tmp = s.split(" ");
            if(tmp[0].equals("I")){
                len++;
                minq.add(Integer.valueOf(tmp[1]));
                maxq.add(Integer.valueOf(tmp[1]));
                
            } else {
                if(len == 0)
                    continue;
                len--;
                if(tmp[1].equals("-1")){
                    minq.poll();
                } else {
                    maxq.poll();
                }
                if(len==0){
                    minq = new PriorityQueue<>();
                    maxq = new PriorityQueue<>(Collections.reverseOrder());
                }
            }
        }
        if(len>0){
            return new int[] {maxq.peek(),minq.peek()};
        } else{
            return new int[] {0,0};
        }
        
    }
}

힙 큐 자료구조를 사용해서 해결한 문제
주어지는 operations의 길이가 최대 1000000이므로 매번 입력을 받을 때마다 sort할 수는 없다.

그래서 힙을 통해 정보를 누적해 나가면 시간복잡도를 줄일 수 있다.

다만 최대값을 제거하는 경우와 최소 값을 제거하는 경우 두가지가 있으므로 최소 힙, 최대 힙 둘다 사용해야한다.

또 현재 힙에대한 길이 정보를 int 변수를 두어 같이 관리한다. 이렇게 함으로써 저장된 데이터를 모두 꺼낼때 최소 힙, 최대 힙 둘다 초기화 시켜줌으로써 동기화 시켜줄 수 있다.

최대 힙을 위한PriorityQueue<>(Collections.reverseOrder())
잊으면 안된다...