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

먼저 이중우선순위큐를 구현하기 위해서 유의해야 할 점

매번 정렬을 하는 것은 비효율적 (시간초과 문제)

 

풀이 1. 우선순위 큐 2개 (최대힙과 최소힙) 구현

PriorityQueue : 중복값 허용. 삭제 시 중복값 존재하는 경우, 우선순위가 높은 값 하나만 삭제.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = { 0, 0 };

        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());


        for(String cur : operations){
            String[] tmp = cur.split(" ");
            if(tmp[0].equals("I")) {
                Integer x = Integer.parseInt(tmp[1]);
                maxQ.add(x);
                minQ.add(x);
            } else {
                if(maxQ.isEmpty()) continue;
                if(tmp[1].equals("1")) minQ.remove(maxQ.poll());
                else maxQ.remove(minQ.poll());
            }
        }

        if(!maxQ.isEmpty()) {
            answer[0] = maxQ.poll();
            answer[1] = minQ.poll();
        }

        return answer;
    }
}

 

풀이 2. TreeMap 구현

TreeMap의 경우, 원소를 삽입하면 자동 정렬이 되므로 HashMap보다 느리지만, 순서 유지가 필요할 때 유용.

 

lastEntry(): 가장 뒤에 있는 key-value 쌍을 가져올 수 있음

firstEntry(): 가장 앞에 있는 key-value 쌍을 가져올 수 있음

 

getOrDefault()를 사용하여 value를 늘려주는 방식으로 중복값 구현 가능.

만약 값을 삭제하려고 할 때 value가 1이면 완전 삭제를, 2 이상이라면 value를 대체하는 방식으로 구현.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = { 0, 0 };
        TreeMap<Integer, Integer> m = new TreeMap<>();

        for(String cur : operations){
            String[] tmp = cur.split(" ");
            if(tmp[0].equals("I")) {
                Integer x = Integer.parseInt(tmp[1]);
                m.put(x, m.getOrDefault(x, 0) + 1);
            } else {
                Map.Entry<Integer, Integer> e = null;

                if(m.isEmpty()) continue;
                if(tmp[1].equals("1")) e = m.lastEntry();
                else e = m.firstEntry();

                if (e.getValue() == 1) m.remove(e.getKey());  
                else m.put(e.getKey(), m.get(e.getKey()) - 1);
            }
        }

        if(!m.isEmpty()) {
            answer[0] = m.lastEntry().getKey();
            answer[1] = m.firstEntry().getKey();
        }

        return answer;
    }
}