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

Baekjoon 21939 - 문제 추천 시스템 Ver.1 (클릭 시 이동)

문제

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

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

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

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

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

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	1111	369	257	31.768%

입력

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

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

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

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

출력

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

풀이

이 문제를 풀기 위해서는 이중 우선순위 큐 문제를 먼저 풀어 볼 것을 권장한다.

1. 일단 문제를 관리해야 하는데 문제 번호는 중복되지 않는다.
2. recommend 명령어가 들어 왔을 때 사용할 PQ 2개를 생성한다.(가장 어려운 & 가장 쉬운 문제)
3. 문제를 추천할 때 PQ에서 poll을 해보고 관리되고 있는 문제의 정보와 동일하면 출력한다.
4. add 명령어가 들어 왔을 때 중복된 문제번호가 들어오면 난이도를 업데이트한다.

최종 소스코드

import java.io.*;
import java.util.*;

public class BJ_G4_21939_문제_추천_시스템_Version1 {
    static int N, M;
    static int[] data = new int[100001];    // 데이터를 배열로 관리했다.
    static PriorityQueue<Problem> ascPQ = new PriorityQueue<>();    // 난이도 낮은 순
    static PriorityQueue<Problem> descPQ = new PriorityQueue<>(Collections.reverseOrder());    // 난이도 높은 순

    static class Problem implements Comparable<Problem> {
        int p, l;

        public Problem(int p, int l) {
            this.p = p;
            this.l = l;
        }

        @Override
        public int compareTo(Problem o) {
            if (this.l == o.l) {
                return Integer.compare(this.p ,o.p);
            }
            return Integer.compare(this.l, o.l);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();

        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());
            Problem prob = new Problem(p, l);
            data[p] = l;            // 문제 번호에 해당하는 인덱스에 난이도를 저장
            ascPQ.offer(prob);
            descPQ.offer(prob);
        }

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

            if(command.equals("recommend")){
                if(Integer.parseInt(st.nextToken()) == -1){
                    while(true){
                        Problem p = ascPQ.peek();// peek을 쓰는 이유는 문제를 추천해줬다고 문제가 사라지지 않기 떄문.
                        if(data[p.p] == p.l){            // 문제 번호의 난이도가 맞으면 출력
                            sb.append(p.p).append("\n");
                            break;
                        }
                        ascPQ.poll();        // 이미 바뀌거나 solved 되어서 문제와 일치하지 않을 수 있다.
                    }
                }else{
                    while(true){
                        Problem p = descPQ.peek();
                        if(data[p.p] == p.l){
                            sb.append(p.p).append("\n");
                            break;
                        }
                        descPQ.poll();
                    }
                }
            }else if(command.equals("add")){
                int probNo = Integer.parseInt(st.nextToken());
                int probLev = Integer.parseInt(st.nextToken());
                Problem newProb = new Problem(probNo,probLev);
                data[probNo] = probLev;
                ascPQ.offer(newProb);
                descPQ.offer(newProb);
            }else if(command.equals("solved")){
               data[Integer.parseInt(st.nextToken())] = 0;// 문제 난이도는 1보다 크므로 0은 없는 문제라고 정했다.
            }
        }
        System.out.println(sb.toString());
    }

}