[JAVA] 힙 "이중우선순위큐"

우선순위 큐를 두개를 이용해서 풀어야하는 강박관념에 아래와 같이 풀었다.

 

import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];

        //오름차순 우선순위큐
        PriorityQueue<Integer> incQ
                = new PriorityQueue<Integer>((o1, o2) -> o1 - o2);

        //내림차순 우선순위큐
        PriorityQueue<Integer> decQ
                = new PriorityQueue<Integer>((o1, o2) -> o2 - o1);


        for(String op : operations){
            //공백기준 분리
            String[] str = op.split(" ");
            System.out.println(str[0] +" 분리 " +str[1]);

            if(str[0].equals("D")){
                if(decQ.size()==0){
                    break;
                }
                if(str[1].equals("1")){
                    int max = decQ.poll();//최대값 꺼내기
                    incQ.remove(max);
                }else{
                    int min = incQ.poll();
                    decQ.remove(min);
                }
            }
            else if(str[0].equals("I")){
                int input = Integer.parseInt(str[1]);

                decQ.offer(input);
                incQ.offer(input);
            }
            //작업이 완료되면,
        }
        if(incQ.size()==0 && decQ.size()==0){
            answer[0] = 0;
            answer[1] = 0;

            return answer;
        }

        answer[0] = decQ.poll();
        answer[1] = incQ.poll();


        return answer;
    }
}

여기서 기억해야 할 것은 Queue.remove(값)이다.

큐에서 지워야할 값을 찾아서 remove해주는 메소드를 몰라서 한참을 고민했다.

그리고 NullpointerException을 해결하느라 시간이 걸렸는데, 위처럼 if문을 작성하여 null체크를 하면 해결된다.

 

그러나 위처럼 작성한 코드의 경우 성능에 따라 시간초과가 간혹 발생하여 개선방향을 찾아보았다.

 

 

아래의 코드는 jar100.tistory.com/21분의 코드를 참고한 것이다.

import java.util.Comparator;
import java.util.PriorityQueue;

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

        for (String operation : operations) {
            String[] splitOther = operation.split(" ");

            if (splitOther[0].equals("I")) {
                priorityQueueWithMax.add(Integer.parseInt(splitOther[1]));
                priorityQueueWithMin.add(Integer.parseInt(splitOther[1]));
            }

            if (splitOther[0].equals("D")) {
                if (!priorityQueueWithMax.isEmpty()) {
                    if (splitOther[1].equals("1")) {
                        int max = priorityQueueWithMax.peek();
                        priorityQueueWithMax.remove(max);
                        priorityQueueWithMin.remove(max);

                    } else {
                        int min = priorityQueueWithMin.peek();
                        priorityQueueWithMax.remove(min);
                        priorityQueueWithMin.remove(min);
                    }
                }
            }

        }
        if (!priorityQueueWithMax.isEmpty()) {
            answer[0] = priorityQueueWithMax.peek();
            answer[1] = priorityQueueWithMin.peek();

        }
        return answer;
    }
}

위와 같은 방식은 시간복잡도에서 매우 효율적으로 나왔다.

어느 부분에서 차이가생겼는지는 조금 더 연구해봐야겠다.