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

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

1713번: 후보 추천하기

 

저는 구현을 통해 해당 문제를 해결하였습니다.

저는 액자에 있는 사람을 Map에 넣어서 관리하였습니다. key는 사람의 번호, value는 액자에 넣은 시간으로 하였습니다.

추천된 사람이 액자에 없고 Map이 n보다 크다면 Map의 키를 돌면서 추천이 가장 작은 사람을 찾고 같다면 가장 이전에 추천된 사람을 찾아 없애고 이번에 추천된 사람을 넣었습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class BOJ_1713 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int studentCnt = Integer.parseInt(br.readLine());
        int[] recommends = new int[studentCnt];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < studentCnt ; i++){
            recommends[i] = Integer.parseInt(st.nextToken());
        }
        int[] result = cal(recommends,n,studentCnt);
        for(int num : result){
            System.out.print(num+" ");
        }
    }

    private static final int INF = 987654321;
    private static int[] cal(int[] recommends, int n, int studentCnt) {

        Map<Integer,Integer> recommendCnt = new HashMap<>();
        Map<Integer,Integer> time = new HashMap<>();
        for(int i = 0 ; i < studentCnt ; i++){
            int recommend = recommends[i];
            int nowCnt = recommendCnt.getOrDefault(recommend,0);
            nowCnt++;
            if(!time.containsKey(recommend) && time.size() > n - 1){
                int deleteKey = -1;
                int deleteCnt = INF;
                for(int key : time.keySet()){
                    int keyCnt = recommendCnt.get(key);
                    if(deleteCnt > keyCnt){
                        deleteKey = key;
                        deleteCnt = keyCnt;
                    }else if(deleteCnt == keyCnt && time.get(deleteKey) > time.get(key)){
                        deleteKey = key;
                        deleteCnt = keyCnt;
                    }
                }
                recommendCnt.remove(deleteKey);
                time.remove(deleteKey);
            }
            recommendCnt.put(recommend,nowCnt);
            if(!time.containsKey(recommend)){
                time.put(recommend,i);
            }
        }
        int index = 0;
        int[] result = new int[time.size()];
        for(int key : time.keySet()){
            result[index++] = key;
        }
        Arrays.sort(result);
        return result;
    }
}