99클럽 코테 스터디 6일차 TIL - 우선순위큐

항해99 코테 스터디 6일차 문제인 프로그래머스의 '이중우선순위큐'는 최댓값과 최솟값을 둘다 제거 가능한 이중 우선순위큐를 구현하는 문제다. 난이도는 레벨3이며 우선순위큐 2개를 통해 해결할 수 있다.

 

오늘의 문제 - 이중우선순위큐 문제 정보

문제 키워드

- Heap

난이도

- Level 3

 

문제 요약

• 최댓값도 최솟값도 제거할 수 있는 이중 우선순위큐가 있다.
• 연산의 배열이 주어질 때, 연산을 모두 완료한 후에 남은 최댓값과 최솟값을 구하라.

 

문제 풀이 과정  

• PriorityQueue 2개를 만들어서 풀었다. 최댓값이나 최솟값 제거 시에 제거되는 숫자의 인덱스를 저장해서, 반대쪽 큐에서 추후 숫자를 제거할 때 이미 제거된 숫자는 제외하고 연산하도록 하였다.
• 다만 이렇게 풀이하는 경우, 연산의 수가 많아지면 그만큼 제거된 숫자 리스트도 커져서 연산 속도가 느려지게 된다. 이 점을 고려하여 풀이를 수정할 필요가 있다!

코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        
        PQ pq = new PQ();
        for(int i=0; i<operations.length; i++) {
            String op = operations[i];
            String[] strs = op.split(" ");
            
            if (strs[0].equals("I")) {
                int num = Integer.parseInt(strs[1]);
                pq.addNum(new Number(i, num));
            } else if (strs[1].equals("1")) {
                pq.removeMax();
            } else {
                pq.removeMin();
            }
        }
        
        answer[0] = pq.removeMax();
        answer[1] = pq.removeMin();
        
        return answer;
    }
    
    class PQ {
        private PriorityQueue<Number> minHeap = new PriorityQueue<>();
        private PriorityQueue<Number> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        private List<Integer> removeNums = new ArrayList<>();
        
        public PQ() {}
        
        public void addNum(Number number) {
            minHeap.add(number);
            maxHeap.add(number);
        }
        
        public int removeMin() {
            Integer min = null;
            while(min == null && !minHeap.isEmpty()) {
                Number nextMin = minHeap.poll();
                if (!removeNums.contains(nextMin.idx)) {
                    min = nextMin.val;
                    removeNums.add(nextMin.idx);
                }
            }
            return min == null ? 0 : min;
        }
        
        public int removeMax() {
            Integer max = null;
            while(max == null && !maxHeap.isEmpty()) {
                Number nextMax = maxHeap.poll();
                if (!removeNums.contains(nextMax.idx)) {
                    max = nextMax.val;
                    removeNums.add(nextMax.idx);
                }
            }
            return max == null ? 0 : max;
        }
    }
    
    
    class Number implements Comparable<Number>{
        int idx;
        int val;
        
        public Number(int i, int v) {
            idx = i;
            val = v;
        }
        
        @Override
        public int compareTo(Number other) {
            return this.val - other.val;
        }
    }
}