프로그래머스 - 힙 - 이중우선순위큐

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

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

 

package dataStructure.heap;
 
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class 이중우선순위큐 {
    public static void main(String[] args) {
        이중우선순위큐 o = new 이중우선순위큐();
        System.out.println(Arrays.toString(o.solution(new String[]{"I 16","D 1"})));
    }
 
    public int[] solution(String[] operations) {
        Queue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
        Queue<Integer> minQ = new PriorityQueue<>();
 
        for(int i=0; i<operations.length; i++) {
            String[] operation = operations[i].split(" ");
            String operator = operation[0];
            Integer number = Integer.valueOf(operation[1]);
 
            if(operator.equals("I")) {
                maxQ.offer(number);
                minQ.offer(number);
            } else {
                if(number == 1) {
                    minQ.remove(maxQ.poll());
                } else {
                    maxQ.remove(minQ.poll());
                }
            }
        }
 
        return new int[]{maxQ.peek() == null ? 0 : maxQ.peek(), minQ.peek() == null ? 0 : minQ.peek()};
    }
}
 

알고리즘

• 힙
• 우선순위큐를 활용하여 최대값과 최소값을 구할 수 있는지에 대한 문제이다.
• 간단하게 최대값 우선순위큐와 최소값 우선순위큐 두 개를 만들어 활용하면된다.
• 단, 삽입 및 삭제시 두 큐에 동일하게 삽입, 삭제 되어야 한다.