[강의][섹션6.Sorting and Searching] 4. LRU(캐시, 카카오 변형)

인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(김태원) 강의의 문제입니다. 

 

▣ 문제

캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.

철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.

 

LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다.

캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

5 9
1 2 3 2 6 2 3 5 7

▣ 출력예제 1

7 5 3 2 6

 

 

▣  내 풀이

import java.util.*;

class Main {
    public int[] solution(int size, int n, int[] arr) { // 5; 9; 1,2,3,2,6,2,3,5,7 // 답 : 7 5 3 2 6
        int[] cache = new int[size];
        /* 1. cache안에 없는 숫자가 나오면, 차례로 배열에 순서대로 넣는다.
        *  2. 배열안에 있는게 또 나오면 , 그 인덱스를 확인
        *  3. 그 뒤에있는 숫자의 인덱스부터 끝까지 하나씩 줄여 배열에 다시 넣기
        *  4. 3번작업이 끝나면 , cache배열의 숫자가 5미만이면 그 나온 숫자를 맨 뒤에 넣는다.
        *  5. cache배열의 숫자가 5이면 , 하나씩 인덱스 앞으로 땡겨서 넣기
        *  6. 출력은 거꾸로 출력 */
        int idx = 0;
        for (int i = 0; i < n; i++) {

            // 1,2번 작업
            for (int j = 0; j < size; j++) {
                if (cache[j] == arr[i]) {
                    // 3번 작업
                    for (int k = j; k < size-1; k++) {
                        cache[k] = cache[k + 1]; //만약 12345에서 idx가 2이면(숫자3) -> 1245
                    }
                    cache[cache.length-1] = 0;
                    idx--;
                    break;
                }
            }
            // 5번 작업
            if (idx == size) { // 5로 꽉차면
                for (int j = 0; j < idx - 1; j++) { // 0~3 까지 반복문돌기
                    cache[j] = cache[j + 1]; // 13245이면 3245로
                }
                idx--;
            }
            cache[idx++] = arr[i]; // 4번 작업

        }

        // 6번 작업. 거꾸로 출력
        int index = 0;
        int[] cache2 = new int[size];
        for (int i = size-1; i >= 0; i--) {
            cache2[index++] = cache[i];
        }
        return cache2;

    }
}

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

 

▣  선생님 풀이

import java.util.*;
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; // 1. 중복된 수 있는지 인덱스 찾기(pos)
            if(pos==-1){ // 2. 중복된 수 없으면 한 칸씩 뒤로 밀려남
                for(int i=size-1; i>=1; i--){
                    cache[i]=cache[i-1];
                }
            }
            else{ // 3. 중복된 수 있으면 그 자리(pos)부터 뒤로 밀려남
                for(int i=pos; i>=1; i--){
                    cache[i]=cache[i-1];
                }
            }
            cache[0]=x; // 4. 맨 앞의 인덱스는 항상 새로오는 숫자 넣어주기
        }
        return cache;
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int s=kb.nextInt();
        int n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++) arr[i]=kb.nextInt();
        for(int x : T.solution(s, n, arr)) System.out.print(x+" ");
    }
}

LRU의 특성을 살려서 문제를 풀어야 했는데, 나는 그냥 무식하게 원래의 배열 순서대로 넣고, 다시 출력할 때 다시 뒤집는 작업을 했다..ㅎㅎ

 

배열을 순서대로 채우는 것이 아닌, 맨 앞에 채우고 뒤로 밀려나는 형식의 배열 다루는 방법을 숙달시켜놔야겠다. ...!!!