[BOJ] 1713번 후보 추천

문제

www.acmicpc.net/problem/1713

1713번: 후보 추천하기

풀이

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

public class Main {
	static int N, R;
	static int[] reco;
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	Map<Integer, Integer> cntMap = new HashMap<Integer, Integer>();//key : 번호, value : 카운트
    	Map<Integer, Integer> idxMap = new HashMap<Integer, Integer>();//key : 번호, value : 인덱스
    	N = Integer.parseInt(br.readLine());
    	R = Integer.parseInt(br.readLine());
    	reco = new int[R];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<R;i++) 
    		reco[i] = Integer.parseInt(st.nextToken());
    		
    	for(int i=0;i<R;i++) {
    		if(cntMap.containsKey(reco[i])) {//해당 번호 학생 존재할 때
    			cntMap.put(reco[i],cntMap.get(reco[i])+1);
    		}
    		else {//해당 번호 학생 없을 떄
    			if(cntMap.size() >= N){//사진 틀 꽉 찼을 떄
    				int minValue = Integer.MAX_VALUE;
    				int minIdx = Integer.MAX_VALUE;
    				int minIdxKey = 0;
    				for(Integer key : cntMap.keySet()) {
    					if(cntMap.get(key) < minValue) {
    						minValue = cntMap.get(key);
    						minIdxKey = key;
    					}
    						
    				}
    				for(Integer key : idxMap.keySet()) {
    					if(minValue == cntMap.get(key)) {
    						if(minIdx > idxMap.get(key)) {
    							minIdx = idxMap.get(key);
    							minIdxKey = key;
    						}
    					}
    				}
    				cntMap.remove(minIdxKey);
    				idxMap.remove(minIdxKey);
    			}
    			cntMap.put(reco[i], 1);
    			idxMap.put(reco[i], i);
    		}
    	}
    	List<Integer> list = new ArrayList<Integer>(cntMap.keySet());
    	Collections.sort(list);
    	for(Integer key : list)
    		System.out.print(key+" ");
    	System.out.println();
    	
    	
    	
    }
}