[백준] 21939 문제 추천 시스템 Version 1 (Java)

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

난이도: 골드4

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

문제

입력

출력

---

[아이디어]

recommend 명령을 수행할 때 조건이 좀 까롭다. 문제의 번호와 난이도를 저장할 때 우선순위 큐를 여러개 사용하여 풀까 하다가 트리와 셋을 함께 사용하는 방법을 생각해냈다. 

 

TreeMap<Integer, TreeSet<Integer>> Quest = new TreeMap<>();

우선 맵의 키는 문제의 난이도이다. 하나의 난이도에 대해 하나의 셋이 존재하고, 셋에는 문제 번호를 넣어준다.

TreeMap을 사용해서 난이도를 오름차순으로 정렬해주었고, TreeSet을 사용하였기 때문에 문제 번호는 오름차순으로 정렬되어 있다. 

 

그리고 solved 명령을 수행할 때는, 문제 번호를 사용하여 작업을 해야하기 때문에 난이도를 키로 가진 Map으로는 효율성이 좋지 않았다. 문제 번호가 10만까지만 존재하므로 배열을 새로 만들어 문제 번호에 대해 난이도를 저장해주었다.

int [] level = new int [100001];

인덱스는 문제번호를, 그 안에 값은 문제 난이도를 뜻한다. 예를 들어, 19번 문제의 난이도가 45라면 level[19] = 45가 된다.

 

add 명령을 수행할 때는 단순히 난이도와 문제 번호를 넣어주면 되고, solved 명령을 수행할 때는 level을 활용하여 Map에 빠르게 접근해 문제를 지워주었다.

Quest.get(level[p]).remove(p);
// 해당 레벨에 더이상 문제가 없다면 TreeSet 지우기
if(Quest.get(level[p]).size() == 0) {
    Quest.remove(level[p]);
}
// 해당 문제의 레벨 지우기
level[p] = 0;

여기서 문제를 지워줄 때, 난이도에 대한 문제 번호가 더이상 없다면 해당 key-value를 지워줘야 recommend 명령을 수행할 때 NoSuchElementException이 발생하지 않는다.

 

마지막으로 recommend 명령은 아래와 같다.

int x = Integer.parseInt(tokens.nextToken());
if(x == 1) { // 가장 어려운 문제
    l = Quest.lastKey(); // 가장 어려운 레벨
    output.append(Quest.get(l).last() + "\n"); // 가장 큰 문제번호
} else { // 가장 쉬운 문제
    l = Quest.firstKey(); // 가장 쉬운 레벨
    output.append(Quest.get(l).first() + "\n"); // 가장 큰 문제번호
}

여기서 TreeSet의 내장함수인 last와 first를 수행할 때, set이 비어있으면 NoSuchElementException이 발생한다.

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int N, M;
	static int [] level = new int [100001]; // 인덱스: 문제 번호, level[n]: n번 문제의 난이도
	static TreeMap<Integer, TreeSet<Integer>> Quest = new TreeMap<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		for(int i = 0; i < N; i++) {
			tokens = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(tokens.nextToken());
			int l = Integer.parseInt(tokens.nextToken());
			
			if(!Quest.containsKey(l)) {
				Quest.put(l, new TreeSet<>());
			} 
			Quest.get(l).add(p);
			level[p] = l;
		}
		
		M = Integer.parseInt(br.readLine());
		for(int i = 0; i < M; i++) {
			tokens = new StringTokenizer(br.readLine());
			String op = tokens.nextToken();
			switch(op) {
			case "add": // 문제 추가
				int p = Integer.parseInt(tokens.nextToken());
				int l = Integer.parseInt(tokens.nextToken());
				
				if(!Quest.containsKey(l)) {
					Quest.put(l, new TreeSet<>());
				} 
				Quest.get(l).add(p);
				level[p] = l;
				break;
			case "solved": // 문제 삭제
				p = Integer.parseInt(tokens.nextToken());
				Quest.get(level[p]).remove(p);
				// 해당 레벨에 더이상 문제가 없다면 TreeSet 지우기
				if(Quest.get(level[p]).size() == 0) {
					Quest.remove(level[p]);
				}
				// 해당 문제의 레벨 지우기
				level[p] = 0;
				break;
			case "recommend": // 문제 추천
				int x = Integer.parseInt(tokens.nextToken());
				if(x == 1) { // 가장 어려운 문제
					l = Quest.lastKey(); // 가장 어려운 레벨
					output.append(Quest.get(l).last() + "\n"); // 가장 큰 문제번호
				} else { // 가장 쉬운 문제
					l = Quest.firstKey(); // 가장 쉬운 레벨
					output.append(Quest.get(l).first() + "\n"); // 가장 큰 문제번호
				}
				break;
			}
		}
		System.out.println(output);
	}

}