[백준] 1713번 후보 추천하기 (JAVA)

문제

https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 

설명

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

학생 번호, 추천받은 횟수, 추천받은 순서, 게시 유무를 데이터로 가지는 Student 클래스를 만든다.

위의 3번에서 삭제하는 기준이 첫번째가 추천받은 횟수, 두번째가 추천받은 순서이므로 후에 삭제할 사진을 알기 쉽도록 미리 정렬해놓기 위해 compareTo 메소드를 이에 맞춰 구성한다.

리스트 맨 앞에는 추천 횟수가 가장 적고 추천 횟수가 같다면 추천 순서가 낮은 것이 오게 될 것이다.

학생 번호는 100번까지 있고 각 번호에 해당하는 학생 정보를 저장하기 위해 students 배열을 만든다.

사진틀을 나타내기 위해 ArrayList<Student> 형태의 list를 하나 만든다.

class Student implements Comparable<Student> {
    int id;
    int count;
    int timestamp;
    boolean isIn;

    public Student(int id, int count, int timestamp, boolean isIn) {
        this.id = id;
        this.count = count;
        this.timestamp = timestamp;
        this.isIn = isIn;
    }

    @Override
    public int compareTo(Student s) {
        int comp = this.count - s.count;
        if (comp == 0) {
            return this.timestamp - s.timestamp;
        }
        return comp;
    }
}
    
Student[] students = new Student[101];  // 1 ~ 100
List<Student> list = new ArrayList<>();

학생 번호를 하나씩 입력받으면서 해당 번호의 학생이 추천받은 적이 있는지 확인한다.

이미 사진틀에 게시되어 있는지 확인하고 그렇다면 해당 학생의 추천 횟수를 증가시킨다.

그렇지 않다면, 사진틀이 꽉 찼는지 확인해서 꽉 차있는 경우 미리 정렬되어 있는 list의 맨 앞 사진을 지운다.

그리고 현재 추천받은 사진을 사진틀에 게시한다.

StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= total; i++) {
    int id = Integer.parseInt(st.nextToken());
    
    // 처음으로 추천받은 학생이라면
    if (students[id] == null) {
        students[id] = new Student(id, 0, 0, false);
    }

    // 이미 게시되어 있는 경우
    if (students[id].isIn) {
        students[id].count++;
    }
    // 게시되어 있지 않은 경우
    else {
        // 사진틀이 꽉 찬 경우
        if (list.size() == N) {
            Collections.sort(list);
            list.get(0).isIn = false;
            list.remove(0);
        }

        students[id].count = 1;
        students[id].timestamp = i;
        students[id].isIn = true;
        list.add(students[id]);
    }
}

마지막으로, 사진틀에 게시된 사진의 학생 번호를 오름차순으로 출력해야 하므로 정렬을 한 번 더 수행한다.

list.sort(new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.id - s2.id;
    }
});

for (Student student : list) {
    System.out.print(student.id + " ");
}

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, total;

    static class Student implements Comparable<Student> {
        int id;
        int count;
        int timestamp;
        boolean isIn;

        public Student(int id, int count, int timestamp, boolean isIn) {
            this.id = id;
            this.count = count;
            this.timestamp = timestamp;
            this.isIn = isIn;
        }

        @Override
        public int compareTo(Student s) {
            int comp = this.count - s.count;
            if (comp == 0) {
                return this.timestamp - s.timestamp;
            }
            return comp;
        }
    }

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

        N = Integer.parseInt(br.readLine());
        total = Integer.parseInt(br.readLine());

        Student[] students = new Student[101];  // 1 ~ 100
        List<Student> list = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= total; i++) {
            int id = Integer.parseInt(st.nextToken());

            // 처음으로 추천받은 학생이라면
            if (students[id] == null) {
                students[id] = new Student(id, 0, 0, false);
            }

            // 이미 게시되어 있는 경우
            if (students[id].isIn) {
                students[id].count++;
            }
            // 게시되어 있지 않은 경우
            else {
                // 게시판이 꽉 찬 경우
                if (list.size() == N) {
                    Collections.sort(list);
                    list.get(0).isIn = false;
                    list.remove(0);
                }

                students[id].count = 1;
                students[id].timestamp = i;
                students[id].isIn = true;
                list.add(students[id]);
            }
        }

        list.sort(new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                return s1.id - s2.id;
            }
        });

        for (Student student : list) {
            System.out.print(student.id + " ");
        }
    }
}