[프로그래머스] 이중 우선순위 큐 (Java)

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

코딩테스트 연습 - 이중우선순위큐

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer;
        LinkedList<Integer> q=new LinkedList<>();
        for (int i=0; i<operations.length; i++){
            char c=operations[i].charAt(0);
            int num=Integer.parseInt(operations[i].substring(2));
            if (c=='I'){
                q.add(num);
            }
            else if (c=='D'){
                if (q.size()==0) continue;
                Collections.sort(q);
                if (num==1){
                    q.removeLast();
                }
                else if (num==-1){
                    q.removeFirst();
                }
            }
        }
        if (q.size()==0){
            answer=new int[]{0,0};
        }
        else{
            Collections.sort(q);
            answer=new int[]{q.peekLast(), q.peekFirst()};
        }
        return answer;
    }
}

링크드리스트를 이용해서, 뽑을 때 그것을 정렬하여 최소면 앞에 있는 것을 뽑고=>최대면 뒤에 있는 것을 뽑는 식으로 진행했다.

그런데 정석 풀이는 아닌 것 같다.

 

다른 분의 코드를 보니,

큐를 최소 큐, 최대 큐 2개를 만들어서 최소 큐 아이템을 뽑았을 때 최대 큐에서도 그 아이템을 remove 해준다.

최대 큐 아이템을 뽑았을 때도 마찬가지로 진행해준다.

그렇게 하면 O(nlogn) 으로 할 수 있다!

remove() 함수를 기억할것. remove() 함수도 O(logn) 이다.