Today's Algorithm(2018-12-10)

programmers. 이중우선순위큐

이 문제는 PriorityQueue 를 두 개를 쓰면서 삽입할 때는 동시에 넣고, 최대값 삭제할때는 maxheap을 삭제하고, 최소값을 삭제할 때는 minHeap을 삭제하면 쉽게 해결할 수 있는 문제였습니다. 하지만 PriorityQueue 를 두 개를 사용함에 따라 두 개의 큐 안에 있는 값을 잘 파악해야 하는데요. 그 이유는 다음과 같은 상황들 때문입니다.

• maxHeap, minHeap 두 개의 큐 중 하나가 비워질 경우 → 모두가 꺼내어졌을 때입니다.
• 다 꺼내고 나서 의미없는 꺼내는 행위가 행해졌을 때 → 이 행위는 전혀 의미없는 것으로 데이터에 영향을 미쳐서는 안됩니다.

실제 위 두 개의 상황은 코드를 최초 구현하고 나서 제가 미비했던 부분이었습니다. 그럼 이젠 코드를 보도록 하겠습니다.

class Solution {
    private Queue<Integer> minHeap = new PriorityQueue<>();
    private Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private int deleted = 0;
    private int added = 0;

    public int[] solution(String[] operations) {
        for (String operation : operations) {
            parse(operation);
        }

        int[] answer = new int[2];
        if(maxHeap.isEmpty() || minHeap.isEmpty() || added == deleted) {
             answer[0] = 0; answer[1] = 0;
        } else {
            answer[0] = maxHeap.poll(); answer[1] = minHeap.poll();
        }

        return answer;
    }

    private void parse(String operation) {
        StringTokenizer stk = new StringTokenizer(operation);
        String sign = stk.nextToken();
        int num = Integer.parseInt(stk.nextToken());
        if(added == deleted) {
            minHeap.clear();
            maxHeap.clear();
        }
        if(sign.equals("I")) {
            added++;
            minHeap.offer(num);
            maxHeap.offer(num);
        }
        if(sign.equals("D") && !maxHeap.isEmpty() && !minHeap.isEmpty()) {
            deleted++;
            if(num == -1) minHeap.poll();
            if(num == 1) maxHeap.poll();
        }
    }
}

26~29줄에서 clear() 를 사용한 이유는 상황상 값이 모두 다 꺼내진 상황일때 다 없애어서 이후 꺼내는 행위가 의미없도록 만들기 위함입니다. 이를 통해 35줄에서 isEmpty() 메서드로 인해 이 부분이 실행되지 않도록 하였습니다. 그리고 모두 꺼내어졌을 때는 added, deleted 변수와 isEmpty()메서드를 적절히 활용하여 파악할 수 있도록 하였습니다.