[백준/Java] 21939 : 문제 추천 시스템 Version 1

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

 

처음에 문제를 접했을 때 난이도 순으로 정렬을 하고 난이도가 같으면 문제 번호로 정렬을 하면 손쉽게 전체를 정렬할 수 있다고 생각하였습니다. 그래서 하나의 클래스를 만들고 이를 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 Backjoon_21939_문제_추천_시스템_Version_1 {
    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);
    }
}