[JAVA] 백준 22939번 【G4.문제 추천 시스템 Version 1】

문제

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

 

풀이

1️⃣ TreeMap 과 TreeSet을 이용한 풀이

💡 떠오른 Idea

1. 요구사항에 가장 난이도가 낮은 것에서 가장 문제번호가 작은 것과 가장 난이도가 높은 것에서 가장 문제번호가 큰 것을 출력하라고 했다. 따라서, 난이도를 key로 정렬해주는 TreeMap안에 value로 문제 번호의 크기순으로 정렬해주는 TreeSet을 사용하면 되겠다고 판단했다.

2. 또한, solved 요청 시 문제 번호를 입력받아 지워야 하는데, 난이도를 key로서 갖는 경우에 탐색할 수 없으므로
번호를 key 난이도를 value 로 갖는 HashMap 을 추가해서, solved 요청 시 문제 번호에 맞는 난이도를 얻어와서
그 난이도를 바탕으로 TreeMap의 TreeSet에 접근해서 문제를 제거하는 방식으로 구현하였다.

 

 

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

public class Main {
    static TreeMap<Integer, TreeSet<Integer>> mapKeyByLevel = new TreeMap<>();
    static HashMap<Integer, Integer> mapKeyByProblem = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int P = Integer.parseInt(input[0]);
            int L = Integer.parseInt(input[1]);
            addProblem(L, P);
            mapKeyByProblem.put(P, L);
        }


        StringBuilder ans = new StringBuilder();

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

        for (int i = 0; i < M; i++) {

            String[] input = br.readLine().split(" ");
            String cmd = input[0];

            if (cmd.equals("recommend")) {
                int num = Integer.parseInt(input[1]);
                if (num == 1) {
                    // 가장 어려운 레벨에서 문제번호가 가장 큰 것
                    int problem = mapKeyByLevel.get(mapKeyByLevel.lastKey()).last();
                    ans.append(problem + "\n");
                } else if (num == -1) {
                    // 가장 쉬운 레벨에서 가장 문제번호가 작은 것
                    Integer problem = mapKeyByLevel.get(mapKeyByLevel.firstKey()).first();
                    ans.append(problem + "\n");
                }
            } else if (cmd.equals("add")) {

                int P = Integer.parseInt(input[1]);
                int L = Integer.parseInt(input[2]);
                addProblem(L, P);

                mapKeyByProblem.put(P, L);

            } else if (cmd.equals("solved")) {
                int P = Integer.parseInt(input[1]);
                int L = mapKeyByProblem.get(P);

                TreeSet<Integer> problems = mapKeyByLevel.get(L);
                problems.remove(P);
                // 레벨에 해당하는 문제 set이 빈 경우 제거해주어야함, 안그러면 recomment 시 에러 발생
                if (problems.isEmpty()) {
                    mapKeyByLevel.remove(L);
                }
            }
        }

        System.out.println(ans);
    }

    private static void addProblem(int L, int P) {
        // L에 해당하는 문제 모음이 없는 경우 새로 추가
        if (!mapKeyByLevel.containsKey(L)) {
            TreeSet<Integer> problems = new TreeSet<>();
            problems.add(P);
            mapKeyByLevel.put(L, problems);
        // 이미 L에 해당하는 문제 모음집이 있으면 거기에 추가
        } else {
            mapKeyByLevel.get(L).add(P);
        }
    }
}

 

결과

 

TreeMap 과 TreeSet 자료구조를 알고리즘 풀면서 많이 사용하지 않았었는데,

 

어떤 집단에서 최대 최소 값을 요구할 때, 빠르게 해결할 수 있음을 기억하고 있다가 적절하게 잘 사용해야겠다는 생각이 들었다.

 

왜냐하면 매번 정렬하는 것은 비용이 많이 들고, 우선순위큐의 경우에도 최소 혹은 최대를 빠르게 접근할 수 있지만 그 반대의 경우에는 iterator를 사용해야하기 때문에 O(N) 이 걸리기 때문이다.

 

그리고 메서드의 first 나 last 와 같은 명칭이 가독성을 높여준다 생각이 들었다.