[백준] 21939번 : 문제 추천 시스템 Version 1 - 자바(JAVA)

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

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

 

문제 해석

문제 번호, 난이도로 정리되어 있습니다.

명령어는 총 3가지가 존재합니다.

 

recommend x

x가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력합니다.

가장 어려운 문제가 어려 개라면 문제 번호가 큰 것을 출력합니다.

 

x가 -1인 경우 가장 쉬운 문제의 번호를 출력합니다.

만약 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력합니다.

 

add P L

추천 문제 리스트에 난이도가 L인 문제 번호 P를 추가합니다.

 

solved P

추천 문제 리스트에서 문제 번호 P를 제거합니다.

 

문제 풀이 전 설계

Map을 통해서 문제 번호와 난이도를 관리합니다.

이때 난이도를 적절한 자료구조를 통해 관리해주어야 Min, Max를 잘 뽑아낼 수 있을 것 같습니다.

 

우선순위 큐 2개를 활용하여 Min,Max를 추출해내면 될 것 같습니다.

 

또 하나의 방법으로 TreeSet에서 제공하는 last와 first 메서드를 통해 해결할 수 있습니다.

 

코드

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

public class Main_21939_문제추천시스템Version1 {

    public static class Problem implements Comparable<Problem> {
        int idx;
        int level;

        public Problem(int idx, int level) {
            this.idx = idx;
            this.level = level;
        }

        //난이도 순으로 정렬 -> 문제 번호로 정렬
        public int compareTo(Problem o) {

            if (level - o.level == 0) {
                return idx - o.idx;
            } else {
                return level - o.level;
            }
        }

        public String toString() {
            return "idx : " + idx + " level : " + level;
        }
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        TreeSet<Problem> ts = new TreeSet<>();
        Map<Integer, Integer> map = new HashMap<>();
        StringTokenizer st = null;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            int level = Integer.parseInt(st.nextToken());
            ts.add(new Problem(number, level));
            map.put(number, level);
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            if (command.equals("add")) {
                int number = Integer.parseInt(st.nextToken());
                int level = Integer.parseInt(st.nextToken());
                ts.add(new Problem(number, level));
                map.put(number, level);
            }
            if (command.equals("recommend")) {
                if (Integer.parseInt(st.nextToken()) == 1) {
                    System.out.println(ts.last().idx);
                } else {
                    System.out.println(ts.first().idx);
                }
            }

            if(command.equals("solved")) {
                int number = Integer.parseInt(st.nextToken());
                ts.remove(new Problem(number, map.get(number)));
                map.remove(number);
            }
        }
    }
}