[알고리즘] 1713. 후보 추천하기

0. 문제

 

1713번: 후보 추천하기

 

---

1. 문제 이해

 

1. 시뮬레이션
2. 정렬

 

---

2. 오답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1713 {

    static int N;
    static PriorityQueue<Student> frame = new PriorityQueue<>();
    static BufferedReader br;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        solve();
        print();
    }

    static void solve() throws Exception{
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 사진틀 개수

        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()); // 추천 횟수

        st = new StringTokenizer(br.readLine());
        br.close();

        // 시뮬레이션
        int num;
        boolean isExist;
        for(int i=0; i<M; i++){
            num = Integer.parseInt(st.nextToken());
            isExist = false;
            Student target = null;

            // 이미 액자에 있는지 확인 
            for(Student student : frame){
                if(student.num == num){
                    target = student;
                    isExist = true;
                    break;
                }
            }

            if(isExist) { // 액자에 있는 학생 추천
                target.vote(i);
            }else { // 액자에 없는 학생 추천
                target = new Student(num, 1, i);
                if(frame.size() >= N) { // frame 자리에 여유가 없는 경우
                    frame.poll();
                }
                frame.offer(target);
            }


            // debug
            PriorityQueue<Student> tmp = new PriorityQueue<>(frame);
            while(!tmp.isEmpty()) {
                System.out.print(tmp.poll().num+" ");
            }
            System.out.println();
        }

    }

    static void print(){
        List<Integer> output = new ArrayList<>();
        for(Student student : frame){
            output.add(student.num);
        }
        Collections.sort(output);

        StringBuffer sb = new StringBuffer();
        for(int i : output){
            sb.append(i).append(" ");
        }
        System.out.println(sb.toString());
    }


    static class Student implements Comparable<Student> {
        int num;
        int cnt;
        int cur;

        Student (int num, int cnt, int cur){
            this.num = num;
            this.cnt = cnt;
            this.cur = cur;
        }

        void vote (int cur){
            this.cnt++;
            this.cur = cur;
        }

        @Override
        public int compareTo(Student o) {
            Student other = (Student) o;
            if(this.cnt==other.cnt){
                return Integer.compare(this.cur, other.cur);
            }
            return Integer.compare(this.cnt, other.cnt);
        }

    }
}

// test case
3
8
1 1 2 2 3 3 4 4
// 출력
1 
1 
2 1 
2 1 
3 1 2 
3 1 2 
4 1 2 
4 1 2 
1 2 4

frame.offer(target);에서는 정상적으로 정렬을 수행하지만.

 

target.vote(i); Priority Queue가 정렬을 수행하지 않음.

 

안타깝게도 PQ는 값을 변경해도 자동으로 정렬해주지 않는다.

 

제거하고 다시 넣어야 정렬을 수행한다.

 

---

3. 제출

if(isExist) { // 액자에 있는 학생 추천
    frame.remove(target);
    target.cnt++;
    //target.cur=i; <- 게시된 시간을 갱신하면 안된다!
    frame.offer(target);

• frame.remove(target); target.cnt++; frame.offer(target);
  : cnt를 수정한 결과를 바탕으로 다시 정렬하려면 제거하고 다시 넣어야 한다.
• target.cur=i;
  : 게시된 시간을 갱신하면 안 된다!
  : 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1713 {

    static int N;
    static PriorityQueue<Student> frame = new PriorityQueue<>();
    static BufferedReader br;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        solve();
        print();
    }

    static void solve() throws Exception{
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 사진틀 개수

        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()); // 추천 횟수

        st = new StringTokenizer(br.readLine());
        br.close();

        // 시뮬레이션
        int num;
        boolean isExist;
        for(int i=0; i<M; i++){
            num = Integer.parseInt(st.nextToken());
            isExist = false;
            Student target = null;

            // 이미 액자에 있는지 확인 
            for(Student student : frame){
                if(student.num == num){
                    target = student;
                    isExist = true;
                    break;
                }
            }

            if(isExist) { // 액자에 있는 학생 추천
                frame.remove(target);
                target.cnt++;
                //target.cur=i; <- 게시된 시간을 갱신하면 안된다!
                frame.offer(target);
            }else { // 액자에 없는 학생 추천
                target = new Student(num, 1, i);
                if(frame.size() >= N) { // frame 자리에 여유가 없는 경우
                    frame.poll();
                }
                frame.offer(target);
            }

            // debug
            //PriorityQueue<Student> tmp = new PriorityQueue<>(frame);
            //while(!tmp.isEmpty()) {
            //    System.out.print(tmp.poll().num+" ");
            //}
            //System.out.println();
        }

    }

    static void print(){
        List<Integer> output = new ArrayList<>();
        while(!frame.isEmpty()) {
            output.add(frame.poll().num);
        }
        Collections.sort(output);

        StringBuffer sb = new StringBuffer();
        for(int i : output){
            sb.append(i).append(" ");
        }
        System.out.println(sb.toString());
    }


    static class Student implements Comparable<Student> {
        int num;
        int cnt;
        int cur;

        Student (int num, int cnt, int cur){
            this.num = num;
            this.cnt = cnt;
            this.cur = cur;
        }

        @Override
        public int compareTo(Student o) {
            Student other = (Student) o;
            if(this.cnt==other.cnt){
                return Integer.compare(this.cur, other.cur);
            }
            return Integer.compare(this.cnt, other.cnt);
        }

    }
}

 

---