백준 - 후보 추천하기

오늘 풀어본 문제는 ⭐후보 추천하기라는 문제이다.

1. 문제요약

1. 사진틀은 비어있다.
2. 특정 학생 추천 시, 등록된다.
3. 사진틀이 비어있지 않다면 가장 추천횟수가 적은 학생을 삭제한다.
   • 추천횟수가 같다면 가장 오래된 사진을 삭제한다.
   • 삭제된 학생의 추천 수는 0이 된다.
4. 이미 있는 학생이 추천받으면 추천 수가 오른다.

2. 입출력

[입력]

• 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20)
• 총 추천횟수 (1000 이하)
• 추천된 학생의 번호

3. 알고리즘

• pq를 이용하는 문제

4. 코드

오랜만에 Map을 쓰니 좀 헷갈렸다. Map 복습용 문제!

class Info implements Comparable<Info> {
    int num;
    int great;
    int order;

    public Info(int num, int great, int order) {
        this.num=num;
        this.great=great;
        this.order=order;
    }

    @Override
    public int compareTo(Info o){
        if(this.great == o.great)
            return this.order - o.order;
        return this.great - o.great;
    }

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

        int N = Integer.parseInt(br.readLine());
        int greatCnt = Integer.parseInt(br.readLine());

        //번호, 자료구조
        Map<Integer, Info> list = new HashMap<>();

        st = new StringTokenizer(br.readLine());
        int order = 0;
        while (greatCnt --> 0) {
            int now = Integer.parseInt(st.nextToken());
            order++;
            if(list.containsKey(now))
            {
                list.get(now).great++;
                continue;
            }
            if(list.size() >= N && !list.containsKey(now)) {
                Info out = findOut(list);
                list.remove(out.num);
            }
            list.put(now, new Info(now,1, order));
        }

        List<Integer> keys = new ArrayList<>(list.keySet());
        Collections.sort(keys);

        StringBuilder sb = new StringBuilder();
        for (int key : keys) {
            sb.append(key).append(" ");
        }
        System.out.println(sb);
    }

    static Info findOut(Map<Integer, Info> list){
        PriorityQueue<Info> queue = new PriorityQueue<>();

        for(Info value : list.values()){
            queue.add(value);
        }

        return queue.poll();
    }
}