프로그래머스 <이중우선순위큐>

문제

I 숫자 -> 주어진 숫자 삽입
D 1 -> 최댓값 삭제
D -1 -> 최솟값 삭제

마지막에 남아있는 최댓값, 최솟값 반환

접근

1. PriorityQueue를 사용해 값을 채워넣은 뒤 최소 최댓값을 구하려 했다.
2. 최댓값을 구할 때 어떻게 할까 생각하다가 앞의 모든 것을 빼내서 새로운 큐를 만드는 메서드를 따로 구현하였다.

PriorityQueue<Integer> lastDelete(PriorityQueue<Integer> priorityQueue){
	PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
    for (int i = 0; i < pq.size() - 1; i++) {
        priorityQueue.add(pq.poll());
    }
    return priorityQueue;
}

3. 너무 많은 연산이 필요했나보다... 시간이 지나도 답이 안뜬다...
4. 다른 방법을 찾아보던 중 TreeMap을 통해 풀 수 있다는 것을 깨달았다. TreeMap은 key의 값으로 오름차순 자동 정렬이 되고, lastKey() / firstKey()와 같은 기능들이 존재한다.

풀이

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

        TreeMap<Integer, Integer> tm = new TreeMap<>();

        for (String str : operations) {
            int n = Integer.parseInt(str.substring(2, str.length()));
            if (str.charAt(0) == 'I') {
                tm.put(n, tm.getOrDefault(n, 0) + 1);
            } else if (tm.size() == 0) {
                continue;
            } else if (n == 1) {
                tm.remove(tm.lastKey());
            } else {
                tm.remove(tm.firstKey());
            }
        }

		// tm의 크기에 따라 최솟값, 최댓값 구하는 방법이 다르다.
        if (tm.size() >= 2) {
            answer[0] = tm.lastKey();
            answer[1] = tm.firstKey();
        } else if (tm.size() == 1) {
            answer[0] = tm.firstKey();
            answer[1] = tm.firstKey();
        } else {

        }

        return answer;
    }
}

추가

TreeMap을 통해 잘 풀었다고 생각했는데, 위의 PriorityQueue를 통해서 풀 수 있는 방법이 있는 것도 알게 되었다.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
PriorityQueue<Integer> reverse_pq = new PriorityQueue<Integer>(Collections.reverseOrder());

위와 같이 Queue를 두개 만든 뒤 각자에게 값을 넣어준다. 각각 오름차순, 내림차순으로 정렬될 것이다.

또한 이렇게 할 시에 max값은 reverse_pq를 통해서 구할 수 있다.

pq.remove(max);

위의 메서드는 pq에서 max라는 값을 지울 수 있게 해준다. 이 기능을 쓴다면 여러번 반복하지 않아도 PriorityQueue만으로 답을 구할 수 있을 것이다.