4. ★★ Least Recently Used (LRU)

1. 문제

LRU: Least Recently Used 최근에 덜 사용된 것

즉 캐시에서 작업을 제거할 때 기즌은 가장 오랫동안 사용하지 않을 작업을 제거한다.

 

1. Cache Miss: 해야할 작업이 캐시에 없으면 모든 작업이 뒤로 밀리고 새로운 작업이 맨 앞에 위치한다.

2. Cache Hit: 해야할 작업이 캐시에 있으면 있는 작업을 맨 앞에 위치하고 기존의 위치까지 뒤로 민다.

ex) 작업 3 사용시: 5 2 3 1 6 ㅡㅡ> 3 5 2 1 6

 

2 - 1. 나의 풀이

1. Cache Hit 인경우

2. Cache Miss 인경우

나눠서 그대로 코딩했다.

 

 

2- 2. 나의 코드

import java.util.*;
public class Main {
    public static int[] solution(int s, int n, int[] arr) {
        int[] cache = new int[s];
        boolean flag = false;

        for (int i = 0; i < n; i++) {
            int tmp = arr[i];
            //같은 캐시가 있는지 0~cache.length 까지 찾는다.
            for (int j = 0; j < cache.length; j++) {
                flag = false;
                if(tmp == cache[j]){ //같은게 캐시에 있으면 뒤로 미루고 앞으로
                    for (int k = j; k > 0; k--) { //k=0이 되고 k > 0 에서 막히기 때문에 k=0인 상태로 종료
                        cache[k] = cache[k - 1];
                    }
                    cache[0] = tmp; //for문 종료후 cache[0]에 cache[k] = tmp or cache[0] = tmp;
                    flag = true; //캐시 조정이 있었다면 flag == true
                }
                if(flag) break;
            }//조정이 한번도 없었다면 flag는 false인 상태로 나오게 된다.

            if(!flag){ //캐시 조정이 없었다면 flag == false;.
                for (int j = cache.length - 1; j > 0; j--) {
                    cache[j] = cache[j - 1];
                }cache[0] = tmp;
            }
           /* for(int x : cache) System.out.print(x + " ");
            System.out.println();*/
        }



        return cache;
    }

    public static void main(String[] args) {
        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 : solution(s, n, arr)) System.out.print(x + " ");
    }
}

 

 

3 - 1. 강의 풀이

강의에서 중요했던 포인트는

Hit와 Miss는 결국 둘다 cache[i] = cache[i-1] 을 사용한다는 것이다.

i가 배열의 끝에서 부터인지, 아니면 Hit의 경우 작업이 기존에 있었던 인덱스부터인지만 다를 뿐이다.

 

3 - 2. 강의 코드

package Sort;

import java.util.*;
public class Sort_04_solution {
    public static int[] solution(int[] arr, int s, int n) {
        int[] cache = new int[s];

        for (int x : arr) {
            int pos = -1;
            for (int i = 0; i < s; i++) if(x == cache[i]) pos = i;
            if(pos == -1){ //같은 값을 찾지 못했다면 즉, Cache Miss
                for (int i = s-1; i > 0; i--) {
                    cache[i] = cache[i - 1];
                }
                cache[0] = x;
            }else{
                for (int i = pos; i > 0; i--) {
                    cache[i] = cache[i - 1];
                }
                cache[0] = x;
            }
        }


        return cache;
    }

    public static void main(String[] args) {
        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 : solution(arr, s, n)) System.out.print(x + " ");
    }
}

3 - 3. 수강생 코드

어느 수강생 분께서 올린 코드인데 이게 결국 훨씬 간결하다.

package Sort;

import java.util.*;
public class Sort_04_solution {
    public static int[] solution(int[] arr, int s, int n) {
        int[] cache = new int[s];
        
        for (int x : arr) {
            int pos = s - 1; //Miss 일 경우 pos = 캐시의 크기 -1;
            for(int i =0; i<s;i++)if(x==cache[i])pos=i; //Hit이면 pos = i;
			
            //Hit이든 Miss 이던 결국 밀어내고 cache[0] = x 는 같으므로.
            for (int i = pos; i > 0; i--) cache[i] = cache[i - 1];
            cache[0]=x;
        }

        return cache;
    }

    public static void main(String[] args) {
        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 : solution(arr, s, n)) System.out.print(x + " ");
    }
}

 

 

4. 얻어갈 점

1. 공통적인 부분을 활용하자.

2. answer = "NO"를 선언하고 조건문에서 return "YES"를 하듯 pos = n - 1 (Miss인 경우 미리 선언) Hit인 경우 pos = i;

를 활용 해 더 간결하게 코드를 짤 수 있다.