백준 1713번 후보 추천하기

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

우선순위 큐를 사용해야 하는지 고민이었다.
하지만 큐에서 너무 자주 빼야해서 비효율적.
n, m의 크기 상 배열에 넣고 시뮬레이션 돌리는 것이 더 효율적이다.

구현순서
1. 후보 사진이 존재?
2. 존재하면 cnt 올리고 없으면 cnt=1로 새로 넣기
3. 후보 사진이 없는 경우
4. 사진이 꽉 차있지 않다면 그냥 추가 아니라면 제거 후 추가
5. 제거 대상 찾기 (기준 = target)
6. 제거 대상 비교 -> target의 cnt보다 작으면 제거 대상
7. target과 cnt가 같다면 time이 더 오래된 것이 제거 대상

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


class Candidate{
    int num,cnt,time;
    Candidate(int num, int cnt, int time){
        this.num = num;
        this.cnt = cnt;
        this.time = time;
    }
}

public class Main {
    int n,r;
    List<Candidate> list = new ArrayList<>();
    List<Integer> answer = new ArrayList<>();

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    void solution() throws Exception {
        n = Integer.parseInt(br.readLine());
        r = Integer.parseInt(br.readLine());

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

        for(int i=0;i<r;i++){
            int num = Integer.parseInt(st.nextToken());
            boolean exist = false;

            for(Candidate c:list){
                if(c.num==num){ //이미 있는 후보
                    c.cnt++;
                    exist = true;
                    break;
                }
            }

            //없는 후보면 그냥 추가 or 제거 후 추가
            if(!exist){
                if(list.size()<n){ //그냥 추가
                    list.add(new Candidate(num,1,i));
                }
                else{ //제거 후 추가
                    //제거 대상 찾기
                    Candidate target = list.get(0); //제일 앞 후보 가져오기

                    for(Candidate c:list){
                        if(c.cnt<target.cnt){
                            target = c;
                        }
                        else if(c.cnt==target.cnt){
                            if(c.time<target.time){
                                target = c;
                            }
                        }
                    }

                    list.remove(target);
                    list.add(new Candidate(num,1,i));
                }
            }
        }

        for(Candidate c:list){
            answer.add(c.num);
        }

        Collections.sort(answer);

        for(int a:answer){
            System.out.print(a+" ");
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}