백준 21939 - 문제 추천 시스템
문제 파악
문제집에 난이도가 다른 문제가 여러 개 있는데 그 중 가장 어려운 문제 혹은 가장 쉬운 문제를 추천해주는 문제
- 명령어를 통해 문제 추가, 삭제, 추천 가능
- add P L : 문제 번호 P, 난이도 L을 추가
- solved P : 문제 번호 P 문제집에서 제거
- recommend x :
x가 1이면 가장 어려운 문제 번호 출력
x가 -1이면 가장 쉬운 문제 번호 출력
문제 특성 상 자유롭게 정렬, 넣었다 빼기가 가능해야 하므로 덱을 사용해야 할 것 같았는데 생각해보니 덱은 양 끝에서만 가능하기 때문에 힙을 사용해야 한다. 최대힙, 최소힙으로 최댓값, 최소값을 쉽게 찾을 수 있다.
먼저 힙은 완전이진트리를 따른다 - 부모 노드가 자식 노드를 최대 두개까지 가지고 있으면서 마지막 레벨을 제외한 나머지 노드가 완전히 채워진 형태의 트리
최대 힙 : 부모 노드가 자식 노드보다 항상 클 경우
- 삽입의 경우 맨 끝에 삽입되어 부모 노드보다 클 경우 루트쪽으로 계속 교환하며 올라감
- 삭제의 경우 루트 노드가 삭제되고 가장 마지막 노드가 루트 노드로 올라온 후 제자리를 찾아갈 수 있도록 교환하며 내려감
- 최소 힙도 반대로 연산 가능
풀이
- 문제의 개수 N과 문제들(번호 P, 난이도 L)을 입력받는다.
a. 문제를 두 힙에 넣는다.(최대힙과 최소힙)
b. 삭제된 문제를 체크하기 위해 해시맵에 키(문제번호), 값(난이도)를 기록해둔다.StringTokenizer를 사용해 입력을 쪼개서 받는다. 구분자를 따로 지정해주지 않으면 공백이 기본 구분자
문제번호 - 우선순위 큐의 정렬 기준을 커스텀한다.
a. 최대힙의 경우 먼저 난이도가 높은 것부터 내림차순 정렬
b. 만약 난이도가 같다면 문제 번호가 큰 것부터 내림차순 정렬
c. 최소힙의 경우 먼저 난이도가 낮은 것부터 오름차순 정렬
d. 만약 난이도가 같다면 문제 번호가 작은 것부터 내림차순 정렬 - 명령어 개수 M과 명령어들을 입력받는다.
a. 만약 add 명령어일 경우 (add 문제번호 난이도) 입력
b. solved 명령어일 경우 (solved 문제번호) 입력
c. recommend 명령어일 경우 (recommend 1 or -1) 입력 - 명령어를 수행한다.
a. add 명령어일 경우 최대힙, 최소힙, 해시맵에 추가
b. solved 명령어일 경우 해시맵에서 제거
c. recommend 명령어에 x가 1일 경우 해시맵에 남아있는 문제인지 찾은 후 최대힙의 루트 노드를 반환 후 제거
d. recommend 명령어 x가 -1일 경우에도 남아있는 문제인지 확인 후 최소힙의 루트 노드 반환 후 제거 - 스트링빌더에 넣어놓은 출력값들을 모두 출력
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class 문제_추천_시스템_Version_1 {
static class Problem {
int num, level;
public Problem(int num, int level) {
this.num = num;
this.level = level;
}
}
public static void main(String[] args) throws IOException{
//입력을 많이 받기 때문에 속도가 빠른 버퍼리더 선택
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
PriorityQueue<Problem> maxHip = new PriorityQueue<>((a, b) -> {
//먄약 문제의 난이도가 같으면
if (a.level == b.level) {
//번호가 큰것부터 내림차순 정렬
return b.num - a.num;
} else {
return b.level - a.level;
}
});
PriorityQueue<Problem> minHip = new PriorityQueue<>((a, b) -> {
if (a.level == b.level) {
return a.num - b.num;
} else {
return a.level - b.level;
}
});
Map<Integer, Integer> problemMap = new HashMap<>();
int N = Integer.parseInt(bf.readLine());
for (int i=0; i<N; i++) {
//문자를 쪼개서 받기 위해 사용
StringTokenizer st = new StringTokenizer(bf.readLine());
int P = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
Problem problem = new Problem(P, L);
maxHip.add(problem);
minHip.add(problem);
problemMap.put(P, L);
}
int M = Integer.parseInt(bf.readLine());
for (int i=0; i<M; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine());
String command = st.nextToken();
if (command.equals("add")) {
int P = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
Problem problem = new Problem(P, L);
maxHip.add(problem);
minHip.add(problem);
problemMap.put(P, L);
} else if (command.equals("solved")) {
int P = Integer.parseInt(st.nextToken());
problemMap.remove(P);
} else if (command.equals("recommend")) {
int x = Integer.parseInt(st.nextToken());
if (x == 1) {
while (true) {
Problem top = maxHip.peek();
//문제가 해시맵에 존재하고 해시맵에 있는 문제의 난이도가 최대힙 루트 노드의 난이도와 같다면
if (problemMap.containsKey(top.num) && problemMap.get(top.num) == top.level) {
//최대힙 루트 노드 출력
sb.append(top.num).append("\n");
break;
}
maxHip.poll();
}
} else {
while (true) {
Problem top = minHip.peek();
if (problemMap.containsKey(top.num) && problemMap.get(top.num) == top.level) {
sb.append(top.num).append("\n");
break;
}
minHip.poll();
}
}
}
}
System.out.println(sb);
}
}