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

접근

나는 입력 부분과 알고리즘 처리 구분을 구분하기 위해 추천 후보를 따로 배열에 저장했다. 그리고 추천 시 해당 후보를 바로바로 찾기 위해 map을 사용했고 만약 어떤 후보를 지워야 한다면 그냥 map에서 remove해주었다. 

 

어떤 후보를 지워야하는 경우에는 (1)사진틀이 꽉 차있고 (2)이번에 추천받은 후보가 사진틀에 없다는 조건을 만족해야 한다. 사진틀의 최대 개수는 20개이기 때문에 전부 탐색해주었다. n개를 비교하며 추천횟수가 더 적거나, 만약 같다면 더 오래된 후보를 지우도록 한다. 최종 후보 결과를 출력할 때는 배열에 넣고 정렬해도 되겠지만, 나는 우선순위 큐를 사용하여 저장하는 동시에 값이 정렬되도록 했다. 

 

코드

package week9;

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

public class BJ1713 {
    static class Candidate {
        int num; // 후보 번호
        int recommendCnt; // 추천 횟수
        int registerTime; // 사진이 등록된 시점

        Candidate(int num, int registerTime){
            this.num = num;
            this.registerTime = registerTime;
        }
    }

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

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[] recommendArr = new int[m];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++)
            recommendArr[i] = Integer.parseInt(st.nextToken());

        // 추천 순서대로 작업
        Map<Integer, Candidate> candidateMap = new HashMap<>();

        for (int i = 0; i < m; i++) {
            int key = recommendArr[i];
            
            // 비어있는 사진틀이 있는지 확인
            if(candidateMap.size() == n && candidateMap.get(key) == null){
                Candidate eraseCandidate = null;

                for(Candidate cur : candidateMap.values()){
                    if(eraseCandidate == null) eraseCandidate = cur;
                    // 추천 횟수가 적은 후보를 지움
                    else if(eraseCandidate.recommendCnt > cur.recommendCnt)
                        eraseCandidate = cur;
                    // 추천 횟수가 같으면 더 오래된 사진을 지움
                    else if(eraseCandidate.recommendCnt == cur.recommendCnt &&
                            eraseCandidate.registerTime > cur.registerTime)
                        eraseCandidate = cur;
                }

                candidateMap.remove(eraseCandidate.num);
            }

            // 추천받은 학생의 사진을 게시
            Candidate candidate = candidateMap.getOrDefault(key, new Candidate(key, i));
            candidate.recommendCnt++;
            candidateMap.put(key, candidate);
        }

        // 최종 후보의 학생 번호를 출력
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(Candidate cur : candidateMap.values())
            pq.add(cur.num);

        while(!pq.isEmpty())
            System.out.print(pq.poll() + " ");
    }
}