[백준 7662번] 이중 우선순위 큐 - java

문제 설명

1. 테스트 케이스가 T번 주어진다. 해당 테스트 케이스들에 우선 순위 큐에 시도학 연산 N번이 주어진다.

2. I는 입력, D는 삭제이고 D에서 -1이면 최소값, 1은 최대값을 삭제한다. D시도 시 큐가 비어있으면 연산하지 않는다.

3. 각 테스트 케이스마다 최대값과 최소값을 구하면 된다. 참고로 큐가 비어있으면 EMPTY를 출력한다.

풀이 과정

 1. 문제가 우선순위 큐이기 때문에 가장 간단히 구현할 수 있는 우선순위 큐를 사용하면 시간 초과가 난다....???

 2. 문제의 난이도 자체는 별로 어려울 것이 없다. 분기를 여러 번 하면 된다.

D일때 -> 비어있으면 continue, 아니면 1과 -1에 따라 삭제하기

I면 그냥 add하기

 3. 그렇지만 우선순위 큐로는 구하려 하면 에러가 나기 때문에...TreeMap을 사용해야 한다.

 3. 딱히 설명할 내용이 없다.... 주석으로 적어둠

실패한 코드(1)

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	// 솔직히 말해서 Scanner가 속도가 느리긴 하지만... 코테 단계에서 여기서 시간초과가 나는건 좀 아니라고 생각해서 이걸 자주 쓴다.
	// 프로그래머스 쓰는 이유도 이거다..
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	for(int i=0; i<T; i++){
	// PQ를 총 두개 선언해서 오름차순, 내림차순으로 사용한다. 두 큐를 하나처럼 삭제 및 추가하면 된다고 생각함.
	PriorityQueue<Integer> bigpq = new PriorityQueue<>(Collections.reverseOrder());
	PriorityQueue<Integer> smallpq = new PriorityQueue<>();
	int N = sc.nextInt();
	for(int j=0; j<N; j++){
	String oper = sc.next();
	int num = sc.nextInt();
	if(oper.equals("D")){ // D연산 시
	if(bigpq.isEmpty()) continue; // 둘은 한몸으로 생각하니 하나라도 비어있으면 continue
	else if(num==1){ // 비어있지 않고 큰 수 삭제
	int bigOne = bigpq.poll();
	smallpq.remove(bigOne); // 큰 수에서 삭제한 것에 해당하는 숫자를 작은 쪽에서 삭제한다. <- 여기서 시간복잡도가 O(n)이 된다.
	}else{ // 작은 수 삭제
	int smallOne = smallpq.poll();
	bigpq.remove(smallOne);
	}
	}else{
	bigpq.add(num); // 추가. 참고로 add도 시간복잡도가 많이 들어간다 한다.
	smallpq.add(num);
	}
	}
	if(bigpq.isEmpty()) System.out.println("EMPTY");
	else System.out.println(bigpq.poll() + " " + smallpq.poll());
	}
	}
	}

view raw wrong1 hosted with ❤ by GitHub

실패한 코드(2)

	import java.util.*;
	import java.io.*;
	public class Main {
	public static void main(String args[]) throws IOException {
	// bufferedReader, offer로 시간을 줄여보려 했으나 이 또한 실패함.
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	for(int i=0; i<T; i++){
	PriorityQueue<Integer> bigpq = new PriorityQueue<>(Collections.reverseOrder());
	PriorityQueue<Integer> smallpq = new PriorityQueue<>();
	int N = Integer.parseInt(br.readLine());
	for(int j=0; j<N; j++){
	String input[] = br.readLine().split(" ");
	String oper = input[0];
	int num = Integer.parseInt(input[1]);
	if(oper.equals("D")){
	if(bigpq.isEmpty()) continue;
	else if(num==1){
	int bigOne = bigpq.poll();
	smallpq.remove(bigOne);
	}else{
	int smallOne = smallpq.poll();
	bigpq.remove(smallOne);
	}
	}else{
	bigpq.offer(num);
	smallpq.offer(num);
	}
	}
	if(bigpq.isEmpty()) System.out.println("EMPTY");
	else System.out.println(bigpq.poll() + " " + smallpq.poll());
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

성공한 코드

	import java.util.*;
	import java.io.*;
	public class Main {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(br.readLine());
	for(int i=0; i<T; i++){
	// 최소, 최대의 값을 가지고 있는 트리맵을 사용해 풀었다.
	// 이를 사용하면 최소나 최대를 제거하거나 가져올 때에 O(logn)밖에 시간이 걸리지 않아 기존보다 효율적일 것이라 생각하였다.
	// <값, 개수>를 갖는 tm생성
	TreeMap<Integer, Integer> tm = new TreeMap<>();
	int N = Integer.parseInt(br.readLine());
	for(int j=0; j<N; j++){
	String input[] = br.readLine().split(" ");
	String oper = input[0];
	int num = Integer.parseInt(input[1]);
	if(oper.equals("D")){
	if(tm.isEmpty()) continue;
	else if(num==1){ // 큰 수를 삭제하는 경우
	int minNum = tm.lastKey(); // 제일 작은 수를 가져오고
	int cntNum = tm.get(minNum); // 그 수가 몇개 있는지 확인하여
	if(cntNum == 1) tm.remove(minNum); // 1개만 있으면 그냥 지우고
	else tm.put(minNum, cntNum-1); // 그보다 많으면 숫자를 하나 줄여준다.
	}else{ // 작은수도 로직은 똑같다.
	int minNum = tm.firstKey();
	int cntNum = tm.get(minNum);
	if(cntNum == 1) tm.remove(minNum);
	else tm.put(minNum, cntNum-1);
	}
	}else{
	tm.put(num, tm.getOrDefault(num, 0)+1); // 현재 수를 입력하고, 없으면 생성, 있으면 cnt늘리기
	}
	}
	if(tm.isEmpty()) System.out.println("EMPTY");
	else System.out.println(tm.lastKey() + " " + tm.firstKey());
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub