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

Gold IV

문제(출처: https://www.acmicpc.net/problem/21939)

---

< 문제 추천 시스템 Version 1 >

 

문제 풀이 

 

TreeMap과 HashMap을 사용해서 문제를 해결했다.

 

TreeMap의 사용방법은 아래와 같다.

https://melody-coding.tistory.com/317

[자료구조] TreeMap

 

 

TreeMap에 key값으로 문제 난이도를, value 값으로 TreeMap을 넣어주었다. value 값으로 TreeMap을 사용한 이유는 난이도가 같을 경우 문제의 번호가 크고 작은 것을 판단하기 위해 사용했다. value 값의 TreeMap에는 key값으로 문제 번호를, vlaue 값으로는 의미 없는 -1 값을 넣어주었다. 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class _21939_ { // 문제 추천 시스템 Version 1

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		TreeMap<Integer, TreeMap<Integer, Integer>> map = new TreeMap<>();
		HashMap<Integer, Integer> num = new HashMap<>();

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			int p = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());

			num.put(p, l);

			if (map.containsKey(l)) {
				map.get(l).put(p, -1);
			} else {
				TreeMap<Integer, Integer> temp = new TreeMap<>();
				temp.put(p, -1);
				map.put(l, temp);
			}
		}
		int m = Integer.parseInt(bf.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			String cmd = st.nextToken();
			if (cmd.equals("recommend")) {
				int x = Integer.parseInt(st.nextToken());
				if (x == 1) {
					bw.write(map.lastEntry().getValue().lastKey() + "\n");
				} else {
					bw.write(map.firstEntry().getValue().firstKey() + "\n");
				}

			} else if (cmd.equals("add")) {
				int p = Integer.parseInt(st.nextToken());
				int l = Integer.parseInt(st.nextToken());

				num.put(p, l);

				if (map.containsKey(l)) {
					map.get(l).put(p, -1);
				} else {
					TreeMap<Integer, Integer> temp = new TreeMap<>();
					temp.put(p, -1);
					map.put(l, temp);
				}

			} else {
				int p = Integer.parseInt(st.nextToken());
				if (num.containsKey(p)) {
					int l = num.get(p);
					map.get(l).remove(p);
					if (map.get(l).size() == 0) {
						map.remove(l);
					}
				}
			}
		}
		bw.flush();
	}
}

 

Main

변수)
n : 문제의 개수
map : TreeMap <문제 난이도 l , TreeMap <문제 번호 p, -1>>
num : HashMap <문제 번호 p, 문제 난이도 l>
p : 문제 번호
l : 문제 난이도
m : 명령문의 개수

 

- 문제의 개수(n) 입력

- 문제의 개수만큼 문제 번호(p)와 문제 난이도(l) 입력

: 문제 번호에 해당하는 문제 난이도를 쉽게 찾기 위해 HashMap에 추가

: TreeMap에 문제 난이도를 key 값으로 가지고 있는지 없는지 판단 후 있으면 value 값에 추가, 없으면 TreeMap을 만들어 value에 추가

- 명령문의 개수(m) 입력

- 명령문의 개수만큼 명령문 입력

: recommend 

1) 1인 경우 가장 어려운 문제를 찾기 위해 TreeMap에서 lastEntry를 찾은 후 문제 번호가 큰 lastKey 값을 출력

2) -1인 경우 가장 쉬운 문제를 찾기 위해 TreeMap에서 firstEntry를 찾은 후 문제 번호가 작은 firstKey 값을 출력

: add 

1) 문제 번호에 해당하는 문제 난이도를 쉽게 찾기 위해 HashMap에 추가

2) TreeMap에 문제 난이도를 key 값으로 가지고 있는지 없는지 판단 후 있으면 value 값에 추가, 없으면 TreeMap을 만들어 value에 추가

: solved

1) 문제 번호를 제거하기 위해 HashMap에서 문제에 해당하는 난이도를 찾음

2) TreeMap에서 1)에서 찾은 난이도에 해당하는 value 값에서 그 문제를 제거

3) 문제를 제거한 후 value 값이 하나도 없다면 key 값 제거

- 답 출력

---

---