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

수연이의 도움을 많이 받은 풀이! 자바에 익숙하지 않다는 게 느껴지는 점이 ArrayList를 처음 써봤다ㅎㅎ; 앞으로 익숙해지면 되는거니까!
각설하고, 알고리즘~~~

• 중요! ArrayList는 길이가 가변적이다.

• 알고리즘

(1) 각 operation을 parsing하여 Insert할 number를 ArrayList에 넣는다.
(2-1) Insert 연산의 경우 ArrayList에 number를 넣고 sort한다.
(2-2) Delete 연산의 경우 ArrayList에서 최댓값/최솟값을 제거한다.
(3) ArrayList가 비어있는 경우 {0, 0}, 비어있지 않은 경우 최댓값/최솟값을 return한다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        ArrayList<Integer> num = new ArrayList<>();

        for(int i=0; i<operations.length; i++){
            String oper = operations[i];
            String[] info = oper.split(" ");
            String mode = info[0];
            int number = Integer.parseInt(info[1]);

            if(mode.equals("I")){
                num.add(number);
                Collections.sort(num);
            } else if(mode.equals("D")){
                if(number == 1 && !num.isEmpty()) { // delete max value
                    num.remove(Collections.max(num));
                } else if(number == -1 && !num.isEmpty()){ // delete min value
                    num.remove(Collections.min(num));
                }
            }        
        }

        if(num.isEmpty()) return answer;
        else {
            answer[0] = Collections.max(num);
            answer[1] = Collections.min(num);
        }

        return answer;
    }
}

• 다른 풀이

두 우선순위 큐를 이용하여 구현할 수도 있다. 하나는 오름차순 우선순위 큐, 하나는 내림차순 우선순위 큐이다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minQ = new PriorityQueue<>();

        for(int i=0; i<operations.length; i++){
            String oper = operations[i];
            String[] info = oper.split(" ");
            String mode = info[0];
            int number = Integer.parseInt(info[1]);
            if(mode.equals("I")){
                maxQ.add(number);
                minQ.add(number);
            } else if(mode.equals("D")){
                if(number == 1) {
                    if(!maxQ.isEmpty()) {
                        minQ.remove(maxQ.poll());
                    }
                } else if(number == -1){
                    if(!minQ.isEmpty()) {
                        maxQ.remove(minQ.poll());
                    }
                }
            }
        }

        if(minQ.isEmpty() && maxQ.isEmpty()) {
          answer[0] = 0;
          answer[1] = 0; 
        } else {
            answer[0] = maxQ.peek();
            answer[1] = minQ.peek();
        }

        return answer;
    }
}