[BOJ] 문제 추천 시스템 Version 1

 

 

문제

문제 추천 시스템 Version 1, 문제 링크

풀이

적절한 자료 구조를 이용해야 한다.
문제의 조건대로 정렬 상태를 유지하면서 가장 첫번재 요소와 가장 마지막의 요소를 자유롭게 추출할 수 있어야한다.
여러가지의 자료구조를 생각해보았다.

• Dequeue

Dequeue는 앞과 뒤의 요소를 자유롭게 추출할 수 있다.
그러나 정렬상태를 계속해서 유지할 수 없다는 단점이 있다.

• List

인덱스를 통해 요소의 편리한 접근이 가능하다.
Dequeue와 마찬가지로 정렬 상태를 계속 유지할 수 없다.

• PriorityQueue

우선순위 조건을 선언한 후, 최대힙, 최소힙 두가지를 사용하면 풀이 가능하다.

• TreeSet

우선순위 조건 선언으로 정렬상태 유지가능, 및 앞과 뒤 요소를 자유롭게 접근가능하다.

 

 

이러한 이유로 TreeSet을 이용하였다.
이때 solve명령어는 Set의 요소를 모두 접근할 때 시간이 오래걸린다.
따라서 문제 번호와 문제 전체를 매핑하는 Map을 하나 더 선언하여 O(1)로 접근이 가능하게 하여 시간을 줄였다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        TreeSet<Ploblem> set = new TreeSet<>((o1, o2) -> {
            if (o1.level == o2.level) {
                return o2.number - o1.number;
            }
            return o2.level - o1.level;
        });

        Map<Integer, Ploblem> map = new HashMap<>();

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

        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split(" ");
            set.add(new Ploblem(Integer.parseInt(str[0]), Integer.parseInt(str[1])));
            map.put(Integer.parseInt(str[0]), new Ploblem(Integer.parseInt(str[0]), Integer.parseInt(str[1])));
        }

        int P = Integer.parseInt(br.readLine());
        for (int i = 0; i < P; i++) {
            String[] str = br.readLine().split(" ");
            String command = str[0];
            switch(command) {
                case "add":
                    set.add(new Ploblem(Integer.parseInt(str[1]), Integer.parseInt(str[2])));
                    map.put(Integer.parseInt(str[1]), new Ploblem(Integer.parseInt(str[1]), Integer.parseInt(str[2])));
                    break;
                case "solved":
                    int number = Integer.parseInt(str[1]);
                    Ploblem ploblem = map.get(number);
                    set.remove(ploblem);
                    break;
                case "recommend":
                    if (str[1].equals("1")) {
                        System.out.println(set.first().number);
                    } else {
                        System.out.println(set.last().number);
                    }
                    break;
            }
        }
    }

    static class Ploblem {
        int number;
        int level;

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

https://github.com/Win-9/Algorism/tree/main/BOJ/%EB%AC%B8%EC%A0%9C%20%EC%B6%94%EC%B2%9C%20%EC%8B%9C%EC%8A%A4%ED%85%9C%20Version%201