January 18, 2022
백준 문제 링크 : https://www.acmicpc.net/problem/1713
문제의 기능은 거의 LRU를 구현하는 것과 같다. 가장 많이, 최근에 추천받은 학생만 남긴 후 출력시 오름차순으로 출력해야한다.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;
public class B_1713 {
static class Pair{
int num, cnt;
public Pair(int num) {
this.num = num;
this.cnt = 1;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
ArrayList<Pair> arr = new ArrayList<>();
for(int i=0; i<M; i++){
int nextNum = Integer.parseInt(st.nextToken());
int numIdx = - 1;
for(int j=0; j<arr.size(); j++){
if(nextNum == arr.get(j).num){
numIdx = j;
break;
}
}
if(numIdx == -1){
if(arr.size() == N){
// 추천 개수가 가장 적은 학생을 삭제
int min = Integer.MAX_VALUE;
int minIdx = -1;
for(int j=0; j<arr.size(); j++){
if(min > arr.get(j).cnt){
min = arr.get(j).cnt;
minIdx = j;
}
}
arr.remove(minIdx);
}
arr.add(new Pair(nextNum));
} else{
arr.get(numIdx).cnt++;
}
}
Collections.sort(arr, (e1, e2) ->{
return e1.num - e2.num;
});
arr.forEach(el ->{
System.out.print(el.num+" ");
});
}
}