[백준]21939: 문제 추천 시스템 Version1(java)

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

21939번: 문제 추천 시스템 Version 1

문제

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

recommend x$x$	x$x$가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다. 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다.  x$x$가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다. 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.
add P$P$ L$L$	추천 문제 리스트에 난이도가 L$L$인 문제 번호 P$P$를 추가한다. (추천 문제 리스트에 없는 문제 번호 P$P$만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)
solved P$P$	추천 문제 리스트에서 문제 번호 P$P$를 제거한다. (추천 문제 리스트에 있는 문제 번호 P$P$만 입력으로 주어진다.)

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

입력

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 N$N$ 가 주어진다.

두 번째 줄부터 N+1$N + 1$ 줄까지 문제 번호 P$P$와 난이도 L$L$가 공백으로 구분되어 주어진다.

 N+2$N + 2$줄은 입력될 명령문의 개수 M$M$이 주어진다.

그 다음줄부터 M$M$개의 위에서 설명한 명령문이 입력된다.

출력

recommend 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 최소 한번의 recommend 명령어가 들어온다.

제한

•  1≤N,P≤100,000$1 \le N, P \le 100,000$ 
•  1≤M≤10,000$1 \le M \le 10,000$ 
•  1≤L≤100$1 \le L \le 100$, L$L$은 자연수
•  x=±1$x = \pm 1$ 

예제 입력 1 

5
1000 1
1001 2
19998 78
2667 37
2042 55
8
add 1402 59
recommend 1
solved 1000
solved 19998
recommend 1
recommend -1
solved 1001
recommend -1

예제 출력 1 

19998
1402
1001
2667

---

풀이

두개의 우선순위 큐를 만든다.

번호 및 난이도가 높은 거 부터 뽑는 maxPQ 반대인 minPQ를 생성한다.

Map을 사용해서 현재 내가 풀어야하는 문제를 보관한다.

 

1. solve

else if(commend.equals("solved")) {
    int P =  Integer.parseInt(st.nextToken());
    solve.remove(P);
}

 현재 푼 문제를 찾아서 map에서 제거한다.

이 때 PQ는 제거하지 않는데 이유는 PQ는 정렬순으로 볼 수 있는 자료구조이고 특정 값을 지우려면 시간 복잡도가 길기 대문이다.

 

2. add

if(commend.equals("add")) {
    int P = Integer.parseInt(st.nextToken());
    int L = Integer.parseInt(st.nextToken());
    solve.put(P, L);
    maxHeap.add(new MaxHeap(P, L));
    minHeap.add(new MinHeap(P, L));
} 

- 문제가 추가되는 것이므로 map 과 각 PQ에 넣어준다.

 

3. recommend

else if(commend.equals("recommend")) {
    int n = Integer.parseInt(st.nextToken());

    if(n==1) {
        while(true) {
            if(solve.containsKey(maxHeap.peek().P) && solve.get(maxHeap.peek().P) == maxHeap.peek().L) {
                ans.append(maxHeap.peek().P + "\n");
                break;
            }
            maxHeap.poll();
        }
    } else {
        while(true) {
            if(solve.containsKey(minHeap.peek().P) && solve.get(minHeap.peek().P) == minHeap.peek().L) {
                ans.append(minHeap.peek().P + "\n");
                break;
            }
            minHeap.poll();
        }
    }
} 

현재 가장 작은 혹은 큰 난이도를 출력해야하는데 만약 그 난이도의 문제를 풀었을 수 있으므로 map에 있는 값이 나올때까지 제거해준다. (max에서 풀었으면 min에선 제거가 안 된다.)

전체 코드

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

public class BJ_G4_21939_문제추천시스템 {
    static class MaxHeap implements Comparable<MaxHeap>{
        int P; // 문제 번호
        int L; // 문제 난이도

        MaxHeap(int P, int L) {
            this.P = P;
            this.L = L;
        }

        public int compareTo(MaxHeap o) {
            if(this.L == o.L) {
                return o.P - this.P;
            }
            return o.L - this.L;
        }
    }

    static class MinHeap implements Comparable<MinHeap>{
        int P; // 문제 번호
        int L; // 문제 난이도

        MinHeap(int P, int L) {
            this.P = P;
            this.L = L;
        }

        public int compareTo(MinHeap o) {
            if(this.L == o.L) {
                return this.P - o.P;
            }
            return this.L - o.L;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PriorityQueue<MaxHeap> maxHeap = new PriorityQueue<>();
        PriorityQueue<MinHeap> minHeap = new PriorityQueue<>();
        HashMap<Integer, Integer> solve = new HashMap<>();
        StringBuilder ans = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int P = Integer.parseInt(st.nextToken());
            int L = Integer.parseInt(st.nextToken());
            solve.put(P, L);
            /// 1000 3 2000 3 2000 1
            ///
            maxHeap.add(new MaxHeap(P, L));
            minHeap.add(new MinHeap(P, L));

        }

        int M = Integer.parseInt(br.readLine());

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            String commend = st.nextToken();

            if(commend.equals("add")) {
                int P = Integer.parseInt(st.nextToken());
                int L = Integer.parseInt(st.nextToken());
                solve.put(P, L);
                maxHeap.add(new MaxHeap(P, L));
                minHeap.add(new MinHeap(P, L));
            } else if(commend.equals("recommend")) {
                int n = Integer.parseInt(st.nextToken());

                if(n==1) {
                    while(true) {
                        if(solve.containsKey(maxHeap.peek().P) && solve.get(maxHeap.peek().P) == maxHeap.peek().L) {
                            ans.append(maxHeap.peek().P + "\n");
                            break;
                        }
                        maxHeap.poll();
                    }
                } else {
                    while(true) {
                        if(solve.containsKey(minHeap.peek().P) && solve.get(minHeap.peek().P) == minHeap.peek().L) {
                            ans.append(minHeap.peek().P + "\n");
                            break;
                        }
                        minHeap.poll();
                    }
                }
            } else if(commend.equals("solved")) {
                int P =  Integer.parseInt(st.nextToken());
                solve.remove(P);
            }
        }
        System.out.printf(ans.toString());
    }
}