boj21939: 문제 추천 시스템 Version 1

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

 

접근 방법

최근 본 코테와 비슷한 문제였다. 우선순위 큐에 [문제번호, 난이도] 형태로 값을 집어넣고 문제번호나 난이도 조건에 의해 정렬이 되어있다고 가정하자. 만약에, 이 때 무작위의 문제번호를 제거하라고 한다면 어떻게 할 것인가?

코테에서도 그렇고, 이 문제를 처음 접근할 때 이 아이디어를 내지 못해서 틀렸다. 다른 사람의 아이디어를 참고하니 우선순위 큐 이외의 `해쉬맵`을 선언하여 접근한 것을 볼 수 있었다.

 

문제에서 recommend가 1과 -1일 때 각각 조건이 다른데, 어려운 문제를 우선적으로 뽑는 큐와 쉬운 문제를 우선적으로 뽑는 큐가 필요했다. 나는 max_pq, min_pq로 선언해서 각각의 조건에 맞게 세팅을 해주었다. 

 

해쉬맵을 만든 이유는 간단하다. 문제에서 `solved`를 수행할 때, 문제번호 P를 제거를 해야하는데 우선순위 큐의 특성 상 P를 바로 지울 수 없다. 그렇기 때문에 해쉬맵에서 해당 P를 삭제를 먼저 해주는 것이다. 

 

solved가 계속해서 수행되고나서 recommend가 수행되면 해쉬맵과 큐의 불일치가 발생할 것이다.

해쉬맵에는 문제번호가 없는데 큐에는 있다!! 이 말의 뜻은 큐에 있는 문제번호와 해쉬맵의 문제번호가 일치할 때까지 큐의 값을 삭제해줘야하고, 일치할 때 비로소 문제를 출력해주면 된다.

 

직관적인 예시

max_pq = [1000, 1], [1001,2], [19998, 78], [2667,37], [2042,55]가 있을 때,

map 또한 [1000, 1], [1001,2], [19998, 78], [2667,37], [2042,55] 이렇게 가지고 있을 것이다.

 

solved 19998가 실행되면,

map = [1000, 1], [1001,2], [2667,37], [2042,55] 으로 문제번호 19998이 삭제되지만,

max_pq = [1000, 1], [1001,2], [19998, 78], [2667,37], [2042,55]는 그대로이다.

 

이 때, recommend 1을 실행했을 때, max_pq에 있는 문제번호 19998이 map에는 없다. 따라서, max_pq의 현재 문제번호와 난이도가 map과 일치할 때 까지 큐를 삭제하면 된다. (위 케이스의 경우 하나만 삭제해주면 된다.)

 

 

이러한 과정을 max_pq, min_pq 동시에 해주면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class boj21939_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 문제번호, 난이도 형태
        PriorityQueue<int[]> max_pq = new PriorityQueue<>((a,b) -> {
            if (a[1] == b[1]) return b[0] - a[0];
            return b[1] - a[1];
        });

        PriorityQueue<int[]> min_pq = new PriorityQueue<>((a, b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        Map<Integer, Integer> map = new HashMap<>(); // 제거할 때 쓰는 용도

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            max_pq.add(new int[]{a,b});
            min_pq.add(new int[]{a,b});
            map.put(a,b);
        }

        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            String input = br.readLine();
            String [] arr = input.split(" ");

            if (arr[0].equals("add")) {
                int a = Integer.parseInt(arr[1]);
                int b = Integer.parseInt(arr[2]);
                max_pq.add(new int[]{a,b});
                min_pq.add(new int[]{a,b});
                map.put(a,b); // 모두 다 추가해줌
            }

            else if (arr[0].equals("solved")) {
                int a = Integer.parseInt(arr[1]);
                map.remove(a); // 맵에서만 제거해준다.
            }

            else if (arr[0].equals("recommend")) {
                int a = Integer.parseInt(arr[1]);
                if (a == 1) { // 추천리스트에 가장 어려운 번호를 출력
                    while (true) {
                        int num = max_pq.peek()[0];
                        int diff = max_pq.peek()[1];
                        if (map.containsKey(num) && map.get(num) == diff) {
                            sb.append(max_pq.peek()[0]).append("\n");
                            break;
                        }

                        max_pq.poll();
                    }
                }

                else {
                    while (true) {
                        int num = min_pq.peek()[0];
                        int diff = min_pq.peek()[1];
                        if (map.containsKey(num) && map.get(num) == diff) {
                            sb.append(min_pq.peek()[0]).append("\n");
                            break;
                        }

                        min_pq.poll();
                    }
                }
            }
        }
        System.out.println(sb);
    }
}