[Baekjoon] 7662_이중 우선순위 큐

Gold IV

문제(출처: https://www.acmicpc.net/problem/7662)

---

< 이중 우선순위 큐 >

 

문제 풀이 & 생각

 

처음에는 최댓값과 최솟값을 관리하기 위해 우선순위 큐를 2개 선언해서 오름차순, 내림차순 순으로 정렬해서 사용했다. 시간제한도 6초라서 통과할 줄 알았지만 시간초과에 막혀버렸다.

 

몇 번이나 시도해도 해결할 수 없어 다른 방법을 찾다가 JAVA에 TreeMap이 있는 것을 알게 되었다.

TreeMap에 대해 공부하며 정리한 내용이다.

https://melody-coding.tistory.com/317

[자료구조] TreeMap

 

 

TreeMap을 사용해서 최댓값과 최솟값을 관리했다. 하지만 계속해서 틀렸습니다가 출력되었다.

그 이유는 테스트 케이스가 여러 개 일 때 초기화를 안 해준 것과 출력문에서 개행을 빠트려 발생하는 것이었다.

이 부분을 수정해서 통과했다.

 

시간 초과 코드 (Java)

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<String> arr;
	public static void main(String[] args) throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int t=Integer.parseInt(bf.readLine());
		
		PriorityQueue<Integer> queue=new PriorityQueue<>();
		PriorityQueue<Integer> queue2=new PriorityQueue<>(Collections.reverseOrder());
		
		for(int i=0; i<t; i++) {
			int k=Integer.parseInt(bf.readLine());
			for(int j=0; j<k; j++) {
				st=new StringTokenizer(bf.readLine());
				char cmd=st.nextToken().charAt(0);
				int num=Integer.parseInt(st.nextToken());
				
				if(cmd=='I') {
					queue.add(num);
					queue2.add(num);
				}else if(cmd=='D' && queue.size()>0) {
					if(num==1) {
						int temp=queue2.poll();
						queue.remove(temp);
					}else {
						int temp=queue.poll();
						queue2.remove(temp);
					}
				}
			}
			if(queue.size()==0) {
				bw.write("EMPTY\n");
			}else {
				bw.write(queue2.peek()+" "+queue.peek());
			}
		}
		bw.flush();
	}
}

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class _7662_ { // 이중 우선순위 큐 
	static ArrayList<String> arr;
	public static void main(String[] args) throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t=Integer.parseInt(bf.readLine());

		for(int i=0; i<t; i++) {
			TreeMap<Integer, Integer> map=new TreeMap<>();
			int k=Integer.parseInt(bf.readLine());
			for(int j=0; j<k; j++) {
				st=new StringTokenizer(bf.readLine());
				char cmd=st.nextToken().charAt(0);
				int num=Integer.parseInt(st.nextToken());

				if(cmd=='I') {
					if(map.containsKey(num)) {
						map.put(num, map.get(num)+1);
					}else {
						map.put(num, 1);
					}

				}else if(cmd=='D' && map.size()>0) {
					if(num==1) {
						if(map.lastEntry().getValue()==1) {
							map.remove(map.lastKey());
						}else {
							map.put(map.lastKey(), map.lastEntry().getValue()-1);
						}
					}else {
						if(map.firstEntry().getValue()==1) {
							map.remove(map.firstKey());
						}else {
							map.put(map.firstKey(), map.firstEntry().getValue()-1);
						}
					}
				}
			}
			if(map.size()==0) {
				bw.write("EMPTY\n");
			}else {
				bw.write(map.lastKey()+" "+map.firstKey()+"\n");
			}
		}
		bw.flush();
	}
}

 

Main

- 테스트 케이스(t) 입력

- map : 정수를 관리하는 TreeMap <정수, 정수 개수>

- 연산의 개수(k) 입력

- 연산의 개수만큼 연산 나타내는 문자(cmd)와 정수(num) 입력 -> 문자가 I이면 삽입이므로 map에 추가 (같은 값이 존재할 수 있으므로 이미 있는 경우와 없는 경우를 나누어 판단) / 문자가 D이면 삭제이므로 map이 비어있지 않다면 삭제 (같은 값이 여러 개 일 때와 하나일 때를 나누어 판단)

- map이 비어있다면 "EMPTY" 출력 / 비어있지 않다면 최댓값과 최솟값 출력

 

---

---