LRU

만약 캐시의 사이즈가 5이고 작업이 [2, 3, 1, 6, 7] 순으로 저장되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)

1) Cache Miss : 해야 할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번 작업은 캐시의 맨 앞에 위치한다. [5, 2, 3, 1, 6] (7번 작업은 캐시에서 삭제된다.)

2) Cache Hit : 해야 할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용한다면 Cache Hit가 되고, 3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.
[5, 2, 3, 1, 6] ---> [3, 5, 2, 1, 6]

캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시 메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

※ 입력 설명
첫 번째 줄에 캐시의 크기인 S(3 <=S <=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다.
두 번째 줄에 N개의 작업 번호가 처리 순으로 주어진다. 작업 번호는 1 ~100이다.

※ 출력 설명
마지막 작업 후 캐시 메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.

 

삽입정렬을과 배열을 이용해서 푸는 문제

 

먼저 캐시 배열을 돌면서 캐시 안에 작업이 있는지 확인하고 

있으면 히트한 곳의 인덱스를 기억, 그 인덱스부터 1번까지 삽입정렬을

없으면 맨 뒤부터 1번까지 삽입정렬을 하고 

둘다 0번 인덱스에 새 작업을 넣어준다

 

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

class Main {

    public int[] solution(int size, int n, int[] arr){
        int[]cache = new int[size];
        for(int x : arr){
            int pos = -1;
            for(int i = 0; i < size; i++){
                //캐시 안에 작업이 있는 상태면 인덱스를 기억
                if(x == cache[i]) pos = i;
            }

            //미스, 뒤로 다 당기고 맨 앞에 x값 넣어주기
            if(pos == -1){
                for(int i = size-1; i >= 1; i--) {
                    cache[i] = cache[i-1];
                }
                cache[0] = x;
            }

            //hit, pos지점부터 반복문을 돌아서 캐시 값을 당겨주고 맨 앞에 pos위치의 값 넣어주기
            else {
                for(int i = pos; i >= 1; i--){
                    cache[i] = cache[i-1];
                }
                cache[0] = x;
            }
        }
        return cache;
    }



    public static void main(String[] args) {
            Main t = new Main();
            Scanner in = new Scanner(System.in);
            int s = in.nextInt();
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i =0; i <n; i++) arr[i]= in.nextInt();
            for(int x : t.solution(s,n,arr)) System.out.print(x + " ");

    }
}