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

우선순위큐(PriorityQueue) 문제입니다

 

우선순위큐를 두 번 사용하면 해결할 수 있습니다.

첫 번째 우선순위큐에 값들을 저장시키고, 최소값을 빼내는데 사용합니다.(Java는 최소힙이기 때문에 첫 번째 값을 바로 빼낼 수 있습니다.)

두 번째 우선순위큐는 최소 값을 빼내기 위해 사용합니다.

첫 번째 우선순위큐의 원소들을 차례로 하나씩 빼 두 번째에 저장시켜 최대가 아닌 원소를 저장합니다.

첫 번째 우선순위큐의 최대가 제거되었으면 두 번째 우선순위 큐에 옮겨놓은 원소들을 다시 이동시키면 됩니다.

 

[구현 코드]

import java.util.*;

class Solution {
    public static int[] solution(String[] operations) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> tmp = new PriorityQueue<>(); // 임시 저장소

        for (String op : operations) {
            char oc = op.charAt(0);
            int val = Integer.parseInt(op.substring(2));

            if (oc == 'I') {
                pq.add(val);
            } else {
                if (!pq.isEmpty()) {
                    if (val == 1) {
                        // 가장 큰 값을 제외한 갚들을 임시 저장소에 저장
                        while (pq.size() > 1) tmp.add(pq.poll());

                        // 가장 큰 값 제거
                        pq.poll();

                        // 임시 저장소의 값을 다시 옮김
                        while (!tmp.isEmpty()) pq.add(tmp.poll());
                    } else {

                        // 가장 작은 값 제거
                        pq.poll();
                    }
                }
            }
        }

        // 결과 도출
        int min = 0;
        int max = 0;
        if (pq.size() >= 2) {
            min = pq.poll();

            while (pq.size() > 1) pq.poll();

            if (pq.size() == 1) max = pq.poll();
        } else if (pq.size() == 1) {
            max = pq.poll();
            min = max;
        }

        return new int[]{max, min};
    }
}