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

문제

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

처음에 n개의 {문제번호, 문제 난이도} 가 주어진다.

위에 규칙에 따라 구현해주면 된다.

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

---

먼저 생각난것이 이중 우선순위큐를 돌리자고 생각했다.

새로운 클래스를 만드는 것이다.

class Hard implements Comparable<Hard> {
    int num;
    int difficulty;

    public Hard(int num, int difficulty) {
        this.num = num;
        this.difficulty = difficulty;
    }

    @Override
    public int compareTo(Hard h){
        if(h.difficulty == this.difficulty)
            return h.num - this.num;
        return h.difficulty - this.difficulty;
    }
}

class Easy implements Comparable<Easy>{
    int num;
    int difficulty;

    public Easy(int num, int difficulty) {
        this.num = num;
        this.difficulty = difficulty;
    }

    @Override
    public int compareTo(Easy e){
        if(e.difficulty == this.difficulty)
            return this.num - e.num;
        return this.difficulty - e.difficulty;
    }
}

Hard는 어려운 문제를 추천해주는 우선순위큐에, Easy는 쉬운문제를 추천해주는 우선순위큐에 넣어준다.

 

PriorityQueue<Hard>hard = new PriorityQueue<>();
PriorityQueue<Easy>easy = new PriorityQueue<>();

int[]check = new int[100001];
 
 for(int i=0;i<n;i++){
 	st = new StringTokenizer(br.readLine());
   int num = Integer.parseInt(st.nextToken());
   int difficulty = Integer.parseInt(st.nextToken());
   
   hard.add(new Hard(num, difficulty));
   easy.add(new Easy(num, difficulty));
   
   check[num]=difficulty;
}

입력 부분이다.

check 배열에는 문제번호의 난이도가 들어간다.

나중에 문제번호가 삭제되도 새로운 난이도로 들어올 수 있기 때문에 문제번호에 따른 난이도를 저장해주었다.

 

처음에는 문제가 solve되면 단순히 check[num] = false로 해두고 문제를 풀었지만 틀렸다.

왜냐하면 문제번호가 삭제되도 또 똑같은 문제번호가 난이도가 다르게해서 들어올 수 있다. 그렇게 되면 단순히 true, false만으로는 

못잡는다.

따라서 문제번호의 난이도를 넣으면 해결될 수 있다.

 

1) add

명령어가 add이면 hard와 easy에 모두 넣어주고 check 배열을 업데이트 해준다.

 

2) recommend

명령어가 recommend이면 우선순위큐를 돌아보면서 현재 큐의 peek이 check 배열에 저장된 난이도가 맞는지 확인한다.

아니면 해당 peek은 이미 제거 되었기 때문에 큐에서 제거해주고 while 문을 돌며 check배열에 저장된 난이도와 peek이 같은 순간에 

멈추고 peek를 출력해준다.

 

3) solve

check 배열에 문제의 번호에 해당하는 난이도를 0으로 초기화 해준다.

 

StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            if(command.equals("add")){
                int num = Integer.parseInt(st.nextToken());
                int difficulty = Integer.parseInt(st.nextToken());

                hard.add(new Hard(num, difficulty));
                easy.add(new Easy(num, difficulty));

                check[num]=difficulty;
            }
            else if(command.equals("recommend")){
                int flag = Integer.parseInt(st.nextToken());
                if(flag == 1){
                    int num = hard.peek().num;
                    while(check[num] != hard.peek().difficulty){
                        hard.remove();
                        num = hard.peek().num;
                    }
                    sb.append(hard.peek().num).append("\n");
                }
                else {
                    int num = easy.peek().num;
                    while(check[num] != easy.peek().difficulty){
                        easy.remove();
                        num = easy.peek().num;
                    }
                    sb.append(easy.peek().num).append("\n");
                }
            }
            else{
                int num = Integer.parseInt(st.nextToken());
                check[num]=0;
            }
        }

---

전체 코드이다.

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        PriorityQueue<Hard>hard = new PriorityQueue<>();
        PriorityQueue<Easy>easy = new PriorityQueue<>();
        int[]check = new int[100001];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            int difficulty = Integer.parseInt(st.nextToken());

            hard.add(new Hard(num, difficulty));
            easy.add(new Easy(num, difficulty));

            check[num]=difficulty;
        }

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            if(command.equals("add")){
                int num = Integer.parseInt(st.nextToken());
                int difficulty = Integer.parseInt(st.nextToken());

                hard.add(new Hard(num, difficulty));
                easy.add(new Easy(num, difficulty));

                check[num]=difficulty;
            }
            else if(command.equals("recommend")){
                int flag = Integer.parseInt(st.nextToken());
                if(flag == 1){
                    int num = hard.peek().num;
                    while(check[num] != hard.peek().difficulty){
                        hard.remove();
                        num = hard.peek().num;
                    }
                    sb.append(hard.peek().num).append("\n");
                }
                else {
                    int num = easy.peek().num;
                    while(check[num] != easy.peek().difficulty){
                        easy.remove();
                        num = easy.peek().num;
                    }
                    sb.append(easy.peek().num).append("\n");
                }
            }
            else{
                int num = Integer.parseInt(st.nextToken());
                check[num]=0;
            }
        }

        System.out.println(sb);

    }
}
class Hard implements Comparable<Hard> {
    int num;
    int difficulty;

    public Hard(int num, int difficulty) {
        this.num = num;
        this.difficulty = difficulty;
    }

    @Override
    public int compareTo(Hard h){
        if(h.difficulty == this.difficulty)
            return h.num - this.num;
        return h.difficulty - this.difficulty;
    }
}

class Easy implements Comparable<Easy>{
    int num;
    int difficulty;

    public Easy(int num, int difficulty) {
        this.num = num;
        this.difficulty = difficulty;
    }

    @Override
    public int compareTo(Easy e){
        if(e.difficulty == this.difficulty)
            return this.num - e.num;
        return this.difficulty - e.difficulty;
    }
}