[백준][BOJ-7662][자바] 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for(int i=0; i<T; i++) {
			Map<Integer, Integer> map = new HashMap<>();
			PriorityQueue<Integer> min = new PriorityQueue<>();
			PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
			int Q = Integer.parseInt(br.readLine());
			
			for(int j=0; j<Q; j++) {
				st = new StringTokenizer(br.readLine());
				String command = st.nextToken();
				Integer number = Integer.parseInt(st.nextToken());
				
				switch(command){
				case "I":
					map.put(number, map.getOrDefault(number, 0) + 1);
					min.offer(number);
					max.offer(number);
					break;
					
				case "D":
					//값이 비었는데 삭제 할려고 할때
					if(map.size() ==0) continue;
					PriorityQueue<Integer> que = number == 1 ? max : min;
					removeMap(que, map);
				}
			}
			if(map.size() == 0 ) sb.append("EMPTY\n");
			else {
				int n = removeMap(max, map);
				sb.append(n+" "+ (map.size() > 0 ? removeMap(min, map) : n) +"\n");
			}
		}
		
		System.out.println(sb.toString());
	}

	static int removeMap(PriorityQueue<Integer> que, Map<Integer, Integer> map) {
        int num;
        while (true) {
            num = que.poll();
            int cnt = map.getOrDefault(num, 0);

            if (cnt == 0)
                continue;

            if (cnt == 1)
                map.remove(num);
            else
                map.put(num, cnt - 1);

            break;
        }

        return num;
    }
}

 

정리

• 문제의 취지에 맞게 최대 우선순위와 최소 우선순위를 선언해준다.
• Map을 통해 숫자와 해당 숫자의 갯수를 저장한다. insert할 때, map.getOrDefefault를 통해 없다면 0을 반환시켜 +1한 값을 put해주었다.
• delete는 queue에서 poll하며 값을 꺼내고 해당 값이 map에 해당 값이 존재하지 않는다면 반복해서 poll을 진행한다. 만약 존재한다면 map의 value를 하나 감소시킨 값을 다시 put하고 만약 1이라면 map에서 삭제하였다.