Least Recently Used

설명

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

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

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

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

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

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

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

 

입력

첫 번째 줄에 캐시의 크기인 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

힌트

 

문제 해결

 

제목 그대로 가장 최근에 사용되지 않은 것을 제거해가는 것이다. 캐시의 사이즈는 정해져있고, 사용되는 것이 입력되면 앞에서부터 채워지고, 캐시 사이즈를 벗어나면 뒤에껀 제거된다.

 

우선 캐시의 사이즈 S, 작업의 개수 N을 입력받고, 캐시 배열을 S개로 만들어 주었다.

그런 후 캐시 안을 모두 비어있도록 -1로 초기화시켜 주었다.

Scanner in = new Scanner(System.in);
int S = in.nextInt();
int N = in.nextInt();
int[] cache = new int[S];

for(int i = 0; i < S; i++){
    cache[i] = -1; //비어 있도록 초기화
}

 

 

작업이 계속 들어오는데, 만약 이미 캐시 안에 존재하면 최근 위치로 이동되는 것이고, 존재하지 않으면 새로운 것이 들어오며 뒤에 것이 제거되어야 하므로 isExist라는 boolean형 변수를 만들어주었다. 

그리고 for문을 돌며 작업들을 차례로 입력받아 준다. 

그리고 현재 작업의 위치를 나타내는 pos 변수도 지정해준다.

for(int i = 0; i < N; i++) {
    int task = in.nextInt();
    boolean isExist = false;
    int pos = -1;

 

 

그리고 내부 for문에서 캐시 크기만큼 반복하며 현재 작업이 캐시에 이미 있는지 확인한다. 

만약 존재하면 위치를 pos에 저장하고 isExist를 true로 바꿔준다.

for (int j = 0; j < S; j++) {
    if (cache[j] == task) {
        pos = j;
        isExist = true;
        break;
    }
}

 

 

그러고 나서 isExist를 확인해준다.

• 현재 작업이 이미 캐시에 존재한다면, 지금 작업부터 맨 위까지 한 칸씩 뒤로 이동시킨다. (해당 작업을 캐시의 맨 위(앞)로 이동시키기 위해!!)
• 작업이 캐시에 없다면, 모든 작업을 오른쪽으로 한 칸씩 이동시키고 맨 위에 작업을 추가한다.

위 작업을 조건에 따라 처리한 후에는 지금 작업을 캐시의 맨 위에 넣어주면 된다.

if (isExist) {
        for (int k = pos; k > 0; k--) {
            cache[k] = cache[k - 1];
        }
    } else {
        // 캐시 안 작업을 오른쪽으로 이동
        for (int k = S - 1; k > 0; k--) {
            cache[k] = cache[k - 1];
        }
    }
    cache[0] = task;
}

 

 

최종 코드

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P04_LRU { // int형 배열로 푸세욤
    public static void main(String[] args) {
        /** 가장 최근에 사용되지 않은 것을 제거, 맨 앞이 가장 최근에 쓰인 작업
         *  캐시 사이즈가 정해져 있음. 최근 사용된 게 추가되면 마지막은 사라짐. **/

        Scanner in = new Scanner(System.in);
        int S = in.nextInt();
        int N = in.nextInt();
        int[] cache = new int[S];

        for(int i = 0; i < S; i++){
            cache[i] = -1; //비어 있도록 초기화
        }

        for(int i = 0; i < N; i++) {
            int task = in.nextInt();
            boolean isExist = false;
            int pos = -1;

            for (int j = 0; j < S; j++) {
                if (cache[j] == task) {
                    pos = j;
                    isExist = true;
                    break;
                }
            }

            if (isExist) {
                for (int k = pos; k > 0; k--) {
                    cache[k] = cache[k - 1];
                }
            } else {
                // 캐시 안 작업을 오른쪽으로 이동
                for (int k = S - 1; k > 0; k--) {
                    cache[k] = cache[k - 1];
                }
            }
            cache[0] = task;
        }

        for(int i = 0; i < S; i++){
            if(cache[i] != -1)
                System.out.print(cache[i] + " ");
        }

    }
}