[BOJ] 7662 - 이중 우선순위 큐 (Java)

알고리즘

• 자료 구조
• 트리를 사용한 집합과 맵
• 우선순위 큐

1. 문제

요약

• "I n": 큐에 주어진 숫자 n을 삽입
• "D 1" 또는 "D -1": 큐에서 최댓값 또는 최솟값을 삭제
• 만약 큐가 비어있다면, "EMPTY"를 출력

2. Idea

• TreeMap을 사용하여 최소값과 최대값을 구해야 함.

  TreeMap

  TreeMap은 기본적으로 이진 검색 트리
  키를 기준으로 정렬된 상태를 유지

• 문제에서는 TreeMap<Integer, Integer>을 사용하여 숫자와 해당 숫자의 개수를 저장

3. 풀이

3.1. 변수 입력 및 TreeMap 선언

• n 입력
• result=결과값을 저장할 변수로 초기화합니다.
• n_length=n의 자릿수 -> 분해합을 계산할 범위 설정

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());

3.2. 연산 처리

• D 명령어인 경우와 I 명령어인 경우를 구분하여 처리 (if-else)

1. D 명령어인 경우

tm empty -> continue를 통해 다음 명령어를 처리
D 1 -> 최댓값 삭제
lastKey()를 사용하여 가장 큰 키를 가져오고, 해당 키의 개수 확인
개수가 1인 경우 해당 키를 삭제, 그렇지 않은 경우 개수를 1 감소
else -> 최솟값 삭제 (로직은 동일)

2. I 명령어인 경우

tm에 현재 수를 입력, 해당 수가 이미 존재 -> 개수를 1 증가

• 이를 반복하여 각 테스트 케이스에 대한 명령어를 처리
• 해당 테스트 케이스에서의 tm의 상태에 따라 결과를 출력

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늘리기
	}
}

3.3. 결과 출력

if(tm.isEmpty()) System.out.println("EMPTY");
else System.out.println(tm.lastKey() + " " + tm.firstKey());

4. 전체코드

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());
        }

    }
}