배열 밀기, 반복문 밖 판단하기_Least Recently Used

✅ LRU를 생각하며 일의 순서를 구하세요

캐시 메모리는 CPU와 주기억창치 DRAM 사이의 임시 메모리로서 CPU가 처리할 작업을 저장합니다.
캐시메로리 사용 규칙은 LRU, 즉 가장 최근에 사용되지 않은 것을 삭제하는 규칙입니다.
따라서 캐시에서 작업을 제거할 때 가장 오랫동안 사용되지 않은 것을 제거합니다.

캐시의 크기 size가 주어지고, 캐시가 비어있는 상태에서 n개의 작업을 차례대로 처리한다면, n개의 작업이 끝난 후에 캐시 메모리의 상태를 출력하세요

class Main {

    public int[] solution(int size, int n, int[] input){
        int[] cache= new int[size];
        for(int i=0; i<n; i++){
            int pos= -1;
            for(int j=0; j<size; j++){
                if(input[i] == cache[j]) pos=j;
            }

            if(pos == -1){ //cache hit
                for(int l= size-1; l>=1; l--){
                    cache[l]= cache[l-1];
                }
            }
            else{ //cache miss
                for(int k=pos; k>=1; k--){
                    cache[k]= cache[k-1];
                }
            }
            cache[0]= input[i];
        }
        return cache;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int size= sc.nextInt();
        int n= sc.nextInt();
        int[] input= new int[n];
        for(int i=0; i<n; i++){
            input[i]= sc.nextInt();
        }
       for(int i: T.solution(size, n, input)) {
           System.out.print(i+ " ");
       }
    }
}
//⭐️input:
5 9
1 2 3 2 6 2 3 5 7
//⭐️output:
7 5 3 2 6

🔵 ThingsILearned

✔️ Logic

1. 일 처리 순서를 input안에 넣어서 받았다.
   
2. 새롭게 하려는 일이 cache에 있는가? 없는가?를 먼저 확인해야 함
   
3. 확인해서 있으면 pos에다가 어디에 있는지를 저장 pos=j
   
4. 그리고 똑같은 일이 있었던 곳까지 하나씩 밀기
   
5. 확인해서 없으면
   
6. 배열 전체를 하나씩 밀기
   
7. 그리고 배열 가장 처음에 새롭게 하려는 일 저장
   
8. 따라서 4, 6번처럼 새롭게 하려는 일이 있거나 없거나 다 배열을 한 칸씩 밀기는 해야 한다.
   
9. 그러나 있는지, 없는지에 따라 어디서부터 어디까지 밀지가 달라지기 떄문에 새롭게 하려는 일이 배열이 있는지 없는지를 꼭 확인해야 함.
   

✔️ for문으로 ⭐️을 확인해서 for문 밖에 있는 🍎 또는 🌲가 되는가? 판단하기

그런데 🍎 또는 🌲이 또 ⭐️을 판단하는 for문 밖에 있는 경우

먼저 하나의 변수🏀 를 정해둔다.
그리고 ⭐️을 확인해서, ⭐️가 참이면 변수를 바꾸고, ⭐️이 거짓이면 변수를 바꾸지 않는다.
이제 ⭐️에 따라 🍎 또는 🌲를 확인할 차례인데,
이 때 변수만 확인하면 된다.
변수가 바뀌었으면 🍎일 것이고,
변수가 안 바뀌었으면 🌲일 것이기 떄문이다.

    public int[] solution(int size, int n, int[] input){
        int[] cache= new int[size];
        for(int i=0; i<n; i++){
            int pos= -1; //🏀 변수
            for(int j=0; j<size; j++){
                if(input[i] == cache[j]) pos=j;  //⭐️가 참이면 변수를 바꾸기
            }

            if(pos == -1){  //🌲 변수가 안 바뀌었으면
                for(int l= size-1; l>=1; l--){
                    cache[l]= cache[l-1];
                }
            }
            else{  //🍎 변수가 바뀌었으면
                for(int k=pos; k>=1; k--){
                    cache[k]= cache[k-1];
                }
            }
            cache[0]= input[i];
        }
        return cache;
    }