ALGORITHM

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

연듀 2023. 1. 31. 13:59

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

 

1713번: 후보 추천하기

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대

www.acmicpc.net

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Person implements Comparable<Person>{
    int cnt, time, num;
    boolean isIn;

    public Person(int num, int cnt, int time, boolean isIn) {
        this.num = num;
        this.cnt = cnt;
        this.time = time;
        this.isIn = isIn;
    }

    @Override
    public int compareTo(Person o) { // 리스트의 맨 끝부터 사람을 내보낸다.
        int comp1 = o.cnt - cnt;
        if(comp1 == 0){ // 카운트가 같다면
            return o.time - time; // 들어온 순 내림차순
        }
        return comp1;// 카운트 내림차순
    }
}
public class Main {
    static Person[] people;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 사진틀의 개수
        int K = Integer.parseInt(br.readLine());

        people = new Person[101]; // 전체 사람이 들어있는 배열

        List<Person> list = new ArrayList<>(); // 후보자

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(people[num] == null){ // 최초로 불린 사람이라면
                people[num] = new Person(num, 0, 0, false);
            }
            if(people[num].isIn){ // 사진틀에 있는 사람이면
                people[num].cnt++; // 추천받은 횟수만 증가
            }else{ // 사진틀에 없는 사람이면
                if(list.size()==N){ // 사진틀이 가득차있으면 한명 제거해야 함
                    Collections.sort(list);
                    Person removeTarget = list.remove(N-1); // 마지막 사람(추천 받은 횟수가 가장 적은 사람, 같으면 가장 오래된사람)지우기
                    removeTarget.isIn = false; // 빠졌다고 기록
                    removeTarget.cnt = 0;
                }
                people[num].cnt = 1; // 사진틀에 넣음
                people[num].isIn = true;
                people[num].time = i;
                list.add(people[num]);
            }
        }
        Collections.sort(list, (o1, o2) -> {
            return o1.num - o2.num; // 사람 번호 오름차순 정렬
        });

        for (Person person : list) {
            System.out.print(person.num+" ");
        }

    }
}