[인프런 알고리즘] Chapter 06, 4번 문제(Least Recently Used)

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

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec06_04 {
    public static int[] solution(int S, int[] arr) {
        int[] cache = new int[S];
        for (int i : arr)
        {
            int pos = -1;
            for(int j = 0; j < cache.length; ++j) if(cache[j] == i) pos = j; //캐시 히트인지 미스인지 탐색
            if(pos == -1) //Cache Miss
            {
                for(int j = cache.length - 1; j > 0; --j) cache[j] = cache[j - 1]; //모든 작업을 한 칸씩 당긴다.
            }
            else //Chche Hit
            {
                for(int j = pos; j > 0; --j) cache[j] = cache[j - 1]; //pos 부터 맨 앞까지 작업을 한 칸씩 당긴다.
            }
            cache[0] = i; //새로운 작업을 맨 앞에 삽입
        }
        return cache;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < arr.length; ++i) arr[i] = Integer.parseInt(st.nextToken());
        for (int i : solution(S, arr)) System.out.print(i + " ");
    }
}

 

설명

• 캐시 히트/미스 확인
  -arr의 각 작업을 순서대로 탐색하여, 해당 작업이 캐시 내에 있는지(히트) 없는지(미스)를 확인한다.
  -이를 위해 캐시 배열을 탐색하고, 작업이 캐시에 있으면 그 인덱스를 pos에 저장한다. 만약 캐시에 없으면 pos는 -1이 된다.
• 캐시 미스 처리
  -만약 해당 작업이 캐시에 없으면(미스), 캐시 내 모든 항목을 한 칸씩 뒤로 밀어낸 후, 새로운 작업을 캐시의 맨 앞에 삽입한다.
• 캐시 히트 처리
  -작업이 이미 캐시에 있을 경우(히트), 그 작업을 캐시의 맨 앞으로 이동시키기 위해 해당 위치에서부터 앞으로 한 칸씩 당겨온다.