[자바] 백준 21939 - 문제 추천 시스템 Version 1 (boj java)

문제 : boj21939

 

  우선 한글적으로 좀 해맬만한 부분이 있어서 그것부터 써보겠다(제가 그래서 틀렸었단 얘깁니다 ㅠ).

add의 '(추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)' 라는 설명과 solved의 '(추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)' 라는 설명 때문이었다.

 

  결론적으로 '추천 문제 리스트'는 처음 N개의 입력만을 뜻한다. 그리고 '이전에 추천 문제 리스트에 있던 문제 번호'라는 말은 즉, N개에 존재했었으나 solved로 제거된 경우엔 add로 동일한 번호가 들어올 수 있다는 말이었다. 마찬가지로 solved의 설명 또한 해석하자면 결국 N개에 존재했던 녀석들만 solved로 제거가 가능하다는 의미라고 보면 된다. 즉 add로 추가된 녀석들은 solved 되더라도 삭제하면 안된다. 이거 해석하는게 애매해서 결국 단순 구현 문젠데 30분이나 걸려버렸다..

 

---

 

  풀이로 돌아와서 우선 알아야 하는 것들의 리스트를 보자면 다음과 같다.

 

1. 가장 어려운 문제 번호(여러개라면 번호가 높은 것)를 빠르게 알 수 있어야 한다.

2. 가장 쉬운 문제 번호(여러개라면 번호가 낮은 것)를 빠르게 알 수 있어야 한다.

3. 처음 N개의 문제 중 solved를 통해 삭제된 것이 무엇인지 빠르게 알 수 있어야 한다.

 

  '1'은 maxHeap을 사용하면서 Comparator를 잘 정의하면 된다. '2'는 minHeap을 사용하면서 Comparator를 잘 정의하면 된다. '3'에서 '삭제된 목록'은 HashSet을 통해 유지하면 빠르게 확인할 수 있다. 처음 N개의 문제들만 삭제가 가능해야 하기 때문에, 별도로 입력받으면서 처음 N개의 문제에는 마킹을 해두면 '처음 N개의 목록 중 삭제된 목록'을 얻을 수 있다. 그럼 시간복잡도는 대략 O(N+MlogN) 이므로 문제없이 통과할 수 있다. 주의점은 '1'과 '2'에서 '3'을 잘 판단해야 하는 부분이다. 코드의 이하 부분이 해당 역할을 한다.

while (tmp.peek().isRecommendedProblem && solvedProblems.contains(tmp.peek().p)) {
    tmp.poll();
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    class Problem {
        int p, l;
        boolean isRecommendedProblem;
        public Problem(int p, int l) {
            this(p, l, true);
        }
        public Problem(int p, int l, boolean isRecommendedProblem) {
            this.p = p;
            this.l = l;
            this.isRecommendedProblem = isRecommendedProblem;
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Problem> maxHeap = new PriorityQueue<>((o1, o2) -> {
            if (o1.l == o2.l)
                return o2.p - o1.p;
            return o2.l - o1.l;
        });
        PriorityQueue<Problem> minHeap = new PriorityQueue<>((o1, o2) -> {
            if (o1.l == o2.l)
                return o1.p - o2.p;
            return o1.l - o2.l;
        });
        HashSet<Integer> solvedProblems = new HashSet<>();
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while(n-->0) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            Problem problem = new Problem(p, l);
            maxHeap.add(problem);
            minHeap.add(problem);
        }
        int m = Integer.parseInt(br.readLine());
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "add" :
                    int p = Integer.parseInt(st.nextToken());
                    int l = Integer.parseInt(st.nextToken());
                    Problem problem = new Problem(p, l, false);
                    maxHeap.add(problem);
                    minHeap.add(problem);
                    break;
                case "recommend" :
                    int q = Integer.parseInt(st.nextToken());
                    PriorityQueue<Problem> tmp = q==1?maxHeap:minHeap;
                    while (tmp.peek().isRecommendedProblem && solvedProblems.contains(tmp.peek().p)) {
                        tmp.poll();
                    }
                    sb.append(tmp.peek().p).append('\n');
                    break;
                case "solved" :
                    solvedProblems.add(Integer.parseInt(st.nextToken()));
                    break;
            }
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}