알고리즘 - LeastRecentlyUsed

문제

접근

우선 처음 문제를 읽었을 때, 정보처리기사를 취득할 때 많이 나왔던 LRU알고리즘에 대한 얘기였다.

LRU : 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식

1. 처음에는 S개의 메모리를 ArrayList나 Queue등의 자료구조로 풀려고했지만 메모리의 크기가 Over 될때와 아닐때를 구분해야기 때문에 결국 메모리를 배열의 형태로 저장해야된다고 생각했다.

2. 또한 캐시를 한번 돌고나서 현재 메모리 안에 해당 작업이 존재하는지 확인을 해야기 때문에 한바퀴를 돌면서 flag를 주었고 해당 위치정보에 대한 pointer를 줬다.

3. 가장 중요한 1) Cache Miss 일 때와 2) Cache Hit일 때 각자 상황을 나눠서 로직을 돌렸다.

3.1 Cache Miss 이면서 우선 메모리가 다 차지 않을 경우에는 메모리 첫번째부터 작업을 넣고, 추가적으로 들어왔을 때는 뒤로 한 칸씩 가도록 하였다.
3.2 Cache Hit 면은 메모리를 동일하게 뒤로가게 한 후 맨 앞 인덱스에서만 작업을 추가해줬다.

풀이시간 및 후기

약 50 분 ~ 1시간 (포기 안하고 직접 푼 문제)
조건이 많아서 까다롭긴 했는데 그래도 답지를 안보고 풀게되서 기쁘다.. 그래도 점점 하다보니 알고리즘 실력이 느는가 싶어 기분이 좋다. 화이팅!!

Code

package Problem;

import java.util.*;

public class LeastRecentlyUsed2{

    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();
        }

        solution(S, N, arr);
    }

    public static void solution(int S, int N, int arr[]){

        int box[] = new int[S];

        int index = 0;
        int pointer = -1;
        for(int i=0; i<arr.length; i++){

            boolean flag = false;
            for(int j=0; j<S; j++){

                if(arr[i]==box[j]){
                    flag = true;    //해당 원소가 있다.
                    pointer = j;
                    break;
                }
            }
            //다돌았을 때 원소가 없는 것이 확인 됐다면?
            if(!flag){ //0번째 부터 채워나가기

                if(index > box.length-1 ){//박스가 다찼을 때
                    //현재 원소가 없기때문에 맨 뒤에거 빼고 나머지 뒤로 밀린 후  맨앞에 추가
                    for(int k=box.length-1; k>=0 ; k--){
                        if(k!=0) {
                            box[k] = box[k - 1];
                        }else{
                            box[k] = arr[i];
                        }
                    }

                }else { //박스가 다 안찼을 때

                    if(index >= 1) {
                        for (int k = index; k >=1; k--) {
                            box[k] = box[k - 1];
                        }
                        box[0] = arr[i];
                    }else{
                        box[index] = arr[i]; //box에 넣기

                    }
                    index++;            //index위치 한칸 뒤로
                }

            }
            else{//돌았는데 원소가 있는 것이 확인 됐다면? (Cache hit상태)
                for(int k=pointer; k>=0; k--){
                    if(k!=0) {
                        box[k] = box[k-1];
                    }else{
                        box[k] = arr[i];
                    }
                }
            }
        }

        for(int x : box) {
            System.out.print(x+" ");
        }
    }
}