algorithm/Baekjoon Online Judge
[BOJ] 21939 문제 추천 시스템 Version 1(Java)
eo_neunal
2022. 12. 14. 15:25
문제
https://www.acmicpc.net/problem/21939
21939번: 문제 추천 시스템 Version 1
tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령
www.acmicpc.net
풀이
- 문제 번호와 문제 난이도를 저장할 Problem 클래스를 선언하고, 난이도 순 정렬을 위해 Comparable을 구현한다.
- 문제를 난이도 순으로 저장할 TreeSet과 문제 번호와 문제 난이도를 저장할 Map을 선언한다.
- N개의 문제 정보를 입력받아 Problem 객체를 생성해 TreeSet에 추가하고, 문제 번호와 난이도를 각각 Key, Value로 Map에 추가한다.
- M개의 명령어를 입력받아 해당 명령을 수행한다.
- "recommend" 명령어인 경우 x가 1이면 TreeSet에 마지막 값의 문제 번호를 출력하고, x가 -1이면 첫 번째 값을 출력한다.
- "add" 명령어인 경우 문제 정보를 입력받아 Problem 객체를 생성해 TreeSet에 추가하고, 문제 번호와 난이도를 각각 Key, Value로 Map에 추가한다.
- "solved" 명령어인 경우 입력받은 문제 번호로 Map에서 난이도 정보를 가져와 TreeSet에서 해당 Problem을 삭제하고, Map에서도 해당 문제 번호를 삭제한다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Problem implements Comparable<Problem> {
int number;
int level;
public Problem(int number, int level) {
this.number = number;
this.level = level;
}
@Override
public int compareTo(Problem o) {
if (level == o.level) {
return number - o.number;
}
return level - o.level;
}
}
private static final String RECOMMEND = "recommend";
private static final String ADD = "add";
private static final String SOLVED = "solved";
private static final String DELIMITER = " ";
private static final int PROBLEM = 0;
private static final int LEVEL = 1;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
TreeSet<Problem> problems = new TreeSet<>();
Map<Integer, Integer> problemInfo = new HashMap<>();
for (int i = 0; i < n; i++) {
String[] inputs = bufferedReader.readLine().split(DELIMITER);
int number = Integer.parseInt(inputs[PROBLEM]);
int level = Integer.parseInt(inputs[LEVEL]);
problems.add(new Problem(number, level));
problemInfo.put(number, level);
}
StringBuilder answer = new StringBuilder();
int m = Integer.parseInt(bufferedReader.readLine());
for (int i = 0; i < m; i++) {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
String operator = stringTokenizer.nextToken();
int number;
if (operator.equals(RECOMMEND)) {
int x = Integer.parseInt(stringTokenizer.nextToken());
if (x == 1) {
number = problems.last().number;
} else {
number = problems.first().number;
}
answer.append(number).append("\n");
} else if (operator.equals(ADD)) {
number = Integer.parseInt(stringTokenizer.nextToken());
int level = Integer.parseInt(stringTokenizer.nextToken());
problems.add(new Problem(number, level));
problemInfo.put(number, level);
} else if (operator.equals(SOLVED)) {
number = Integer.parseInt(stringTokenizer.nextToken());
int level = problemInfo.get(number);
problems.remove(new Problem(number, level));
problemInfo.remove(number);
}
}
System.out.println(answer);
}
}문제 번호와 난이도를 저장할 자료구조 개선
- 문제 번호와 난이도를 각각 Key, Value로 저장하고 있는 자료구조 Map을 문제 번호를 인덱스로, 난이도를 값으로 저장하는 Array로 수정
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Problem implements Comparable<Problem> {
int number;
int level;
public Problem(int number, int level) {
this.number = number;
this.level = level;
}
@Override
public int compareTo(Problem o) {
if (level == o.level) {
return number - o.number;
}
return level - o.level;
}
}
private static final int[] PROBLEMS = new int[100001];
private static final String RECOMMEND = "recommend";
private static final String ADD = "add";
private static final String SOLVED = "solved";
private static final String DELIMITER = " ";
private static final int PROBLEM = 0;
private static final int LEVEL = 1;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
TreeSet<Problem> problems = new TreeSet<>();
for (int i = 0; i < n; i++) {
String[] inputs = bufferedReader.readLine().split(DELIMITER);
int number = Integer.parseInt(inputs[PROBLEM]);
int level = Integer.parseInt(inputs[LEVEL]);
problems.add(new Problem(number, level));
PROBLEMS[number] = level;
}
StringBuilder answer = new StringBuilder();
int m = Integer.parseInt(bufferedReader.readLine());
for (int i = 0; i < m; i++) {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
String operator = stringTokenizer.nextToken();
int number;
if (operator.equals(RECOMMEND)) {
int x = Integer.parseInt(stringTokenizer.nextToken());
if (x == 1) {
number = problems.last().number;
} else {
number = problems.first().number;
}
answer.append(number).append("\n");
} else if (operator.equals(ADD)) {
number = Integer.parseInt(stringTokenizer.nextToken());
int level = Integer.parseInt(stringTokenizer.nextToken());
problems.add(new Problem(number, level));
PROBLEMS[number] = level;
} else if (operator.equals(SOLVED)) {
number = Integer.parseInt(stringTokenizer.nextToken());
int level = PROBLEMS[number];
problems.remove(new Problem(number, level));
}
}
System.out.println(answer);
}
}문제 정보를 저장할 자료구조 개선
- 문제 정보를 저장하고 있는 자료구조 TreeSet을 각각 오름차순 정렬과 내림차순 정렬이 적용된 두 개의 PriorityQueue로 수정
- N개의 문제 정보를 입력받아 Problem 객체를 생성해 오름차순 정렬 우선순위 큐(최소 힙, MinHeap)와 내림차순 정렬 우선순위 큐(최대 힙, MaxHeap)에 각각 추가하고, 문제 번호를 인덱스로 난이도를 배열에 저장한다.
- M개의 명령어를 입력받아 해당 명령을 수행한다.
- "recommend" 명령어인 경우 x가 1이면 내림차순 정렬된 우선순위 큐에서 문제를 꺼내서 배열에 저장된 해당 문제 번호의 난이도와 해당 문제의 난이도가 같을 때까지 문제를 우선순위 큐에서 삭제하고(이미 해결된 문제 삭제하는 과정), 같으면 문제 번호를 출력한다. x가 -1이면 오름차순 정렬된 우선순위 큐에서 앞선 과정을 반복하여 문제 번호를 출력한다.
- "add" 명령어인 경우 문제 정보를 입력받아 Problem 객체를 생성해 두 우선순위 큐에 추가하고, 문제 번호를 인덱스로 난이도를 배열에 저장한다.
- "solved" 명령어인 경우 입력받은 문제 번호를 인덱스로 난이도를 삭제(난이도는 1이상이기 때문에 0으로 초기화)한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Problem implements Comparable<Problem> {
int number;
int level;
public Problem(int number, int level) {
this.number = number;
this.level = level;
}
@Override
public int compareTo(Problem o) {
if (level == o.level) {
return number - o.number;
}
return level - o.level;
}
}
private static final int[] PROBLEMS = new int[100001];
private static final String RECOMMEND = "recommend";
private static final String ADD = "add";
private static final String SOLVED = "solved";
private static final String DELIMITER = " ";
private static final int PROBLEM = 0;
private static final int LEVEL = 1;
private static final int REMOVE = 0;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
PriorityQueue<Problem> problemsSortedAsc = new PriorityQueue<>();
PriorityQueue<Problem> problemsSortedDesc = new PriorityQueue<>(Comparator.reverseOrder());
for (int i = 0; i < n; i++) {
String[] inputs = bufferedReader.readLine().split(DELIMITER);
int number = Integer.parseInt(inputs[PROBLEM]);
int level = Integer.parseInt(inputs[LEVEL]);
problemsSortedAsc.offer(new Problem(number, level));
problemsSortedDesc.offer(new Problem(number, level));
PROBLEMS[number] = level;
}
StringBuilder answer = new StringBuilder();
int m = Integer.parseInt(bufferedReader.readLine());
for (int i = 0; i < m; i++) {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
String operator = stringTokenizer.nextToken();
if (operator.equals(RECOMMEND)) {
if (Integer.parseInt(stringTokenizer.nextToken()) == 1) {
recommend(problemsSortedDesc, answer);
} else {
recommend(problemsSortedAsc, answer);
}
answer.append("\n");
} else if (operator.equals(ADD)) {
int number = Integer.parseInt(stringTokenizer.nextToken());
int level = Integer.parseInt(stringTokenizer.nextToken());
problemsSortedAsc.offer(new Problem(number, level));
problemsSortedDesc.offer(new Problem(number, level));
PROBLEMS[number] = level;
} else if (operator.equals(SOLVED)) {
PROBLEMS[Integer.parseInt(stringTokenizer.nextToken())] = REMOVE;
}
}
System.out.println(answer);
}
private static void recommend(PriorityQueue<Problem> problems, StringBuilder answer) {
while (true) {
Problem problem = problems.peek();
if (problem.level == PROBLEMS[problem.number]) {
answer.append(problem.number);
break;
}
problems.poll();
}
}
}