[Java]BOJ双優先級キュー(TreeMap)

BOJ G 5双優先級キュー

ヒップホップ

Priority Queue

Tree Map

Gold 5

🔍 問題の説明

https://www.acmicpc.net/problem/7662
デュアルプリオリティキュー(dualpriorityqueue)は、典型的な優先順位キューのように、データを挿入、削除できるデータ構造である.通常のキューとの違いは、データを削除する場合、演算(operation)コマンドに従って最も優先度の高いデータまたは最も低いデータの1つを削除することです.デュアルプライマリ・キューでは、データを挿入する演算と、データを削除する演算の2つの演算が使用されます.削除データの演算は、削除優先度が最も高く、削除優先度が最も低い2つに分けられます.
整数のみを格納する二重優先級隊列Qがあると仮定する.Qに格納される各整数の値自体を優先順位とする.
Qに適した一連の演算が与えられると、それを処理し、書き込みプログラムは最終的にQに格納されたデータの中で最も高価で最も高価であることを出力する.

✔入力

入力データは標準入力を採用している.
入力はT個のテストデータからなる.入力された最初の行は、入力データの数を表す整数Tを与える.
各試験データの最初の行には、Qに適用される演算数を表す整数k(k≦1000000)が与えられる.
次のk行では、演算を表す文字(「D」または「I」)と整数nがそれぞれ与えられる.
「I n」は、整数nをQに挿入する演算を表す.参照同じ整数を挿入できます.
D 1はQから最値を削除する演算を表す.
「D−1」はQから最高値を削除する演算を表す.
最高値(最高値)を削除する演算で、最高値(最高値)が2つ以上の場合は、1つだけ削除することに注意してください.
Qが空で、適用される演算が「D」であれば、この演算は無視できます.Qに記憶されている全ての整数は32ビット整数である.

✔出力

出力は標準出力を採用する.
各テストデータについて、全ての演算が処理された後、Q中の残りの値のうちの最上位値と最大値が出力される.
2つの値を1行に出力し、1つのスペースで区切ります.
Qが空の場合は、「EMPTY」を印刷します.

💡 草。PQ(タイムアウト)

最大ヒップ、最小ヒップの2つのPQを使用.
#1.与えられた演算において、コマンドの最初のアルファベットがIである場合、
minPQ,maxPQはそれぞれ所定の数字を挿入する.

if(command.equals("I")) {
    minPQ.add(num);
    maxPQ.add(num);

#2.最初の文字がDの場合
まず、PQが空であるかどうかを確認し、空である場合、対応する演算を無視します.if(maxPQ.isEmpty()) continue; そしてnumによって最大ヒップから最小ヒップまでそれぞれpollとpollが完了すると、残りの臀部にも同様の数字removeが与えられる.

if(num==1) {
	int tgt = maxPQ.poll();
	minPQ.remove(tgt);
	//큐에서 최댓값을 삭제합니다.
}
else if(num==-1) {
	int tgt = minPQ.poll();
	maxPQ.remove(tgt);
	//큐에서 최솟값을 삭제합니다.
}

最大臀部、最小臀部の2つのPQを用いて問題を解き、結果的にタイムアウトした.
どの部分がタイムアウトになるのか分からないので検索してみました.
各PQでポーリングを行い、別のPQで値を検索して削除します.remove()メソッドを使用してキューを探索して削除します.この部分はタイムアウトしたようです.

💡 草。ソースコード(タイムアウト)

タイムアウトコード

package week19.PRG_Lv3_이중우선순위큐;

import java.util.*;

public class Solution_PRG_Lv3_이중우선순위큐 {
	public static void main(String[] args) {
		System.out.println(solution(new String[] {"I 16", "D 1"}));
	}
	public static int[] solution(String[] operations) {
        int[] answer = new int[2];

        //최대힙,최소힙
        PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(Collections.reverseOrder());
        PriorityQueue<Integer> minPQ = new PriorityQueue<Integer>();
        	
        for (String oper : operations) {
        	String command = oper.split(" ")[0];
        	int num = Integer.parseInt(oper.split(" ")[1]);
			
        	if(command.equals("I")) {
        		minPQ.add(num);
        		maxPQ.add(num);
				//큐에 주어진 숫자를 삽입합니다.
				
			}else if(command.equals("D")){
				
				if(maxPQ.isEmpty()) continue;				
				//빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
				
				if(num==1) {
					int tgt = maxPQ.poll();
					minPQ.remove(tgt);
					//큐에서 최댓값을 삭제합니다.
				}

				else if(num==-1) {
					int tgt = minPQ.poll();
					maxPQ.remove(tgt);
					//큐에서 최솟값을 삭제합니다.
				}
				
			}
		}
        
        //모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 
        if(!maxPQ.isEmpty()) {
        	answer[0] = maxPQ.poll();
        	answer[1] = minPQ.poll();
        }
        return answer;
    }
}

💡 草。TreeMap

TreeMapは、優先キューと探索時間の問題を同時に解決することができる.
TreeMapはKey値に基づいて自動的に昇順に並べられ,ツリー構造の閲覧速度はO(logn)である.firstKey()とlastKey()を利用して、最高価格、最低価格を見つけることができます.
#1.与えられた演算において、コマンドの最初のアルファベットがIである場合、mapに数字を挿入する.

if(command.equals("I")) {
    map.put(num, map.getOrDefault(num, 0)+1); //숫자와 해당 숫자의 개수 저장

#2.最初の文字がDの場合、後の数字が1の場合、最高値-1が削除されます.
削除操作が必要なので、まずマッピングのサイズに値があるかどうかを確認します.if(map.size()==0) continue; 次にmapから最高値、または最高値を削除します.
このとき、削除最値(最切り上げ)の演算に2つ以上の最値(最切り上げ)がある場合は、1つしか削除できません.私はこの点に注意しなかったので,ずいぶん苦労した.

int tgt = ( num==1 ? map.lastKey() : map.firstKey() );
					
int cnt = map.put(tgt, map.get(tgt)-1);
if(cnt==1) map.remove(tgt);

💡 草。ソースコード

package boj.우선순위큐;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main_BJ_7662_이중우선순위큐 {
	static TreeMap<Integer, Integer> map;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			int K = Integer.parseInt(br.readLine());
			map = new TreeMap<>(); 
	        
			for (int k = 0; k < K; k++) {

		        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		        
		        String command = st.nextToken();
		        int num = Integer.parseInt(st.nextToken());
					
		        if(command.equals("I")) {
		        	
		        	map.put(num, map.getOrDefault(num, 0)+1); //숫자와 해당 숫자의 개수 저장
											
				}else if(command.equals("D")){
						
					if(map.size()==0) continue;			
					//빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
					
					int tgt = ( num==1 ? map.lastKey() : map.firstKey() );
					
					int cnt = map.put(tgt, map.get(tgt)-1);
					if(cnt==1) map.remove(tgt);
				}
				
			}
			
			if(map.size()==0) {
				System.out.println("EMPTY");
			}else {
				System.out.println(map.lastKey()+" "+map.firstKey());
			}
			
			
		}
		
	}

}