코딩테스트 및 알고리즘
LRU 알고리즘
영카이브
2024. 1. 30. 23:46
문제.
LRU 알고리즘을 구현하라. LRU 알고리즘은 캐시의 최근 사용 여부에 따라 데이터를 교체하는 알고리즘이며 알고리즘은 가장 최근에 사용된 데이터를 가장 오래된 데이터와 교체하는 방식으로 동작한다.
주어진 데이터 배열을 순회하면서 캐시에 데이터를 저장하는데, 이미 캐시에 해당 데이터가 존재하는 경우 해당 데이터를 최신화하고, 그렇지 않은 경우에는 가장 오래된 데이터를 제거하고 새 데이터를 캐시의 맨 앞에 추가하라. 최종적으로 업데이트된 캐시를 반환하고 출력하여라.
입력 예시
5 9
1 2 3 2 6 2 3 5 7
답 : 7 5 3 2 6
나의 답변
public class Main {
public int[] solution(int size, int n, int[] arr) {
int[] cache =new int[size];
for( int x : arr ) {
// 캐시배열에 데이터가 존재하는지 확인하기위한 targetIdx 변수
int targetIdx=-1;
for( int i=0; i<size; i++ ) if(cache[i]==x) targetIdx=i;
// 캐시배열에 데이터가 존재하지 않을시 전체적으로 한칸 이동한다.
if(targetIdx==-1) {
for(int i=size-1; i>=1; i--) {
cache[i] = cache[i-1];
}
} else {
// 캐시배열에 데이터가 존재할 데이터위치까지 한칸씩 옮긴다.
// 자연스럽게 데이터위치에 있던 자료값은 이전 인덱스에 있던 값으로 채워지기때문에 없어지고 그런 식으로 1번인덱스까지 이어진다.
for(int i=targetIdx; i>=1; i--) {
cache[i] = cache[i-1];
}
}
// 0번 인덱스는 신규데이터값으로 채워진다.
cache[0]=x;
}
return cache;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int n = sc.nextInt();
int[] arr = new int[n];
for( int i=0; i<n; i++ ) {
arr[i] = sc.nextInt();
}
for( int x : T.solution(s, n, arr)) {
System.out.print(x + " ");
}
}
}