설명

캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가

필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.

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

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

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

캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후

캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

코드

public class LeastRecentlyUsed {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();
        int[] arr = new int[input2];
        for(int i=0; i<input2; i++){
            arr[i] = in.nextInt();
        }
        int[] solution = solution(arr, input1);
        for (int i : solution) {
            System.out.print(i+" ");
        }
    }

    public static int[] solution(int[] arr, int k){
        int[] answer = new int[k];
        for(int i : arr){

            int idx = answer.length-1;
            //같은 값이 이미 answer에 존재하는지 확인
            for(int j=0; j<answer.length; j++){
                if(i == answer[j]){
                    idx = j;
                    break;
                }
            }

            for(int j=idx; j>0; j--){
                answer[j] = answer[j-1];
            }
            answer[0] = i;
        }

        return answer;
    }
}

삽입 정렬의 개념을 활용하여 문제를 풀이할 수 있다. 다만 반환될 배열에 값이 현재 삽입될 값과 같다면 그 값은 배열의 0번째로 이동하고 이동한 배열 값보다 앞에 있던 배열들만 모두 1칸씩 뒤로 이동해야하므로 if조건을 잘 사용해주어야한다는 주의점만 지킨다면 답을 구할 수 있다.

문제를 풀이할때 문제의 답만을 구하는 알고리즘이 아닌 문제에서 설명하고 있는 동작을 그대로 구현할 수 있도록 문제를 풀자!