[PG] 이중 우선순위 큐 JAVA

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

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

수행할 명령어들이 담긴 배열 String[] operations가 주어진다.

주어진 명령을 모두 수행한 뒤 남아있는 값 중 최대값, 최소값을 담은 배열을 반환해야한다.

단, 남아있는 값이 하나도 없을 경우 최대값, 최소값은 0으로 한다.

 

명령

I 숫자 : 숫자 입력

D 1 : 입력된 숫자 중 최대값 삭제

D -1 : 입력된 숫자 중 최소값 삭제

 

 

풀이 .

import java.util.*;

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

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for(String operation : operations) {
            StringTokenizer st = new StringTokenizer(operation);
            switch(st.nextToken()) {  // work
                case "I" :  // input
                    int input = Integer.parseInt(st.nextToken());
                    minHeap.add(input);
                    maxHeap.add(input);
                    break;
                case "D" :  // delete
                    if(minHeap.isEmpty()) {
                        continue;
                    }
                    if(st.nextToken().equals("1")) {  // 최대값 삭제
                        int max = maxHeap.poll();
                        minHeap.remove(max);
                    }else {  // 최소값 삭제
                        int min = minHeap.poll();
                        maxHeap.remove(min);
                    }
                    break;
            }
        }

        if(minHeap.isEmpty()) {  // 예외처리
            answer[0] = 0;
            answer[0] = 0;
        }else {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();
        }
        return answer;
    }
}

최대값과 최소값을 동시에 다루기 위해 두 개의 PriorityQueue를 사용하였다.

각 명령을 두 pq에 함께 수행한 뒤 최대, 최소를 반환하면 된다.

pq.remove(Object o)가 가능한 것을 알게 되었다.

 

백준에선 자주 쓰이지만 프로그래머스에서 StringTokenizer 를 사용한 것은 처음이었다.

(StringTokenizer 를 사용해 " "으로 split한 문자열들을 얻을 수 있다. 다른 것으로 split 하고 싶다면 두 번째 매개변수로 줄 수 있다.)