[백준/Java] 21939

문제 추천 시스템 Version 1

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

문제

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

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

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

recommend $x$ :  $x$가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다.
만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다.
$x$가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다. 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.

add $P$ $L$  : 추천 문제 리스트에 난이도가 $L$인 문제 번호 $P$를 추가한다. (추천 문제 리스트에 없는 문제 번호 $P$만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)

solved $P$  : 추천 문제 리스트에서 문제 번호 $P$를 제거한다. (추천 문제 리스트에 있는 문제 번호 $P$만 입력으로 주어진다.)

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

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

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

입력

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

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

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

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

출력

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

제한

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

문제 풀이 방법 및 해설

처음에 문제를 접했을 때 난이도 순으로 정렬을 하고 난이도가 같으면 문제 번호로 정렬을 하면 손쉽게 전체를 정렬할 수 있다고 생각하였다.

그래서 하나의 클래스를 만들고 이를 TreeSet을 통해 정렬을 하려고 하였다. 그런데 solved 명령어를 해결하기 위해서는 문제 번호에 해당하는 TreeSet에 저장된 값을 알아야만 삭제를 O(Log N)에 할 수 있기 때문에 이를 관리하는 HashMap을 생성하였다. HashMap에 키로 문제 번호를 받고 값으로 TreeSet에 저장된 값을 저장하는 방식으로 풀이를 하였다!

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static class Prob implements Comparable<Prob>{
        int number;
        int level;

        public Prob(int number, int level) {
            this.number = number;
            this.level = level;
        }

        @Override
        public int compareTo(Prob p) {
            if(this.level > p.level){
                return -1;
            }else if(this.level < p.level){
                return 1;
            }else{
                if(this.number > p.number){
                    return -1;
                }
                else if(this.number == p.number){
                        return 0;
                }
                else{
                    return 1;
                }
            }
        }
    }



    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        TreeSet<Prob> set = new TreeSet<Prob>();
        HashMap<Integer,Prob> map = new HashMap<>();
        int N = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < N ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            int level = Integer.parseInt(st.nextToken());
            Prob prob = new Prob(number, level);
            set.add(prob);
            map.put(number, prob);
        }

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

        for(int i = 0; i < M ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            if(str.equals("add")){
                int number = Integer.parseInt(st.nextToken());
                int level = Integer.parseInt(st.nextToken());
                Prob prob = new Prob(number, level);
                set.add(prob);
                map.put(number, prob);

            }else if(str.equals("recommend")){
                if(Integer.parseInt(st.nextToken()) > 0){
                    sb.append(set.first().n).append("\n");
                }else{
                    sb.append(set.last().n).append("\n");
                }
            }else{
                int number = Integer.parseInt(st.nextToken());
                set.remove(map.get(number));
                map.remove(number);
            }
        }
        System.out.println(sb);
    }
}