Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Archives
Today
Total
관리 메뉴

전공공부

[BOJ_7662] 이중 우선순위 큐 본문

Study/Problem Solving

[BOJ_7662] 이중 우선순위 큐

monitor 2023. 11. 7. 00:20

설명


맞왜틀을 계속 시도했었던 문제 TestCase 새로 시작되면서 map을 당연히 초기화 해야하는데 그 생각을 못하고 계속 12%에서 틀렸었다.

 

어쨌든 Red Black Tree를 사용하는 TreeMap API를 활용하여서 OlogN으로 찾을 수 있었다. 또한, 최대 값과 최솟 값을 가져오기 정상적으로 가져오기 위해서 같은 수가 두 번 이상 들어올 때와 아예 사라질때 remove가 될때를 주의해서 구현하였다.

 

 

코드


package Data_Structure;

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

public class BOJ_7662 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
        int T = Integer.parseInt(tk.nextToken());
        TreeMap<Integer,Integer> map;
        while(T-- > 0){
            map = new TreeMap<>();
            tk = new StringTokenizer(in.readLine(), " ");
            int N = Integer.parseInt(tk.nextToken());
            while(N-- > 0){
                tk = new StringTokenizer(in.readLine(), " ");

                String str = tk.nextToken();

                int n = Integer.parseInt(tk.nextToken());

                if(str.equals("I")){
                    map.put(n, map.getOrDefault(n, 0) + 1);
                }else if (str.equals("D") && !map.isEmpty()){
                    if(n == -1) {
                    int minKey = map.firstKey();
                    if (map.get(minKey) == 1)
                    {
                        map.remove(minKey);
                    }else{
                        map.put(minKey,map.get(minKey)-1);
                    }
                    }else {
                        int maxKey = map.lastKey();
                        if (map.get(maxKey) == 1)
                        {
                            map.remove(maxKey);
                        }else{
                            map.put(maxKey,map.get(maxKey)-1);
                        }

                    }
                }
            }
            if (map.isEmpty()) {
                System.out.println("EMPTY");
            } else {
                System.out.println(map.lastKey() + " " + map.firstKey());
            }
        }
    }
}

https://www.acmicpc.net/problem/7662

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

 

'Study > Problem Solving' 카테고리의 다른 글

[BOJ_21921] 블로그  (0) 2023.11.08
[BOJ_11728] 배열 합치기  (0) 2023.11.07
[BOJ_2075] N번째로 큰 수  (0) 2023.11.05
[BOJ_22942] 데이터 체커  (1) 2023.11.04
[BOJ_19532] 수학은 비대면강의입니다.  (1) 2023.11.03