[문제풀이] 06-04. LRU

인프런, 자바(Java) 알고리즘 문제풀이

Sorting and Searching - 0604. LRU

🗒️ 문제

🎈 나의 풀이

	private static List<Integer> solution(int n, int[] arr) {
        Queue<Integer> cache = new LinkedList<>();

        for(int i : arr) {
            int l = cache.size();

            for(int j=0; j<l; j++) {
                int work = cache.poll();
                if (work != i) cache.add(work);
            }

            if(cache.size() >= n) cache.remove();
            cache.add(i);
        }

        List<Integer> answer = new ArrayList<>(cache);
        Collections.reverse(answer);
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[m];

        for(int i=0; i<m; i++) arr[i] = sc.nextInt();

        List<Integer> cache = solution(n, arr);

        for(Integer i : cache) System.out.print(i + " ");
    }

🖍️ 강의 풀이

  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;
			if(pos==-1){
				for(int i=size-1; i>=1; i--){
					cache[i]=cache[i-1];
				}
			}
			else{
				for(int i=pos; i>=1; i--){
					cache[i]=cache[i-1];
				}
			}
			cache[0]=x;
		}
		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+" ");
	}

💬 짚어가기

해당 문제는 Queue를 이용하여 풀 수 있다. 나의 풀이에서는 작업이 담긴 배열을 순회하며
해당 작업이 들어왔을 때 캐시 메모리(큐)를 순회하며 검사하도록 구성하였다.

만약 새로 들어온 작업과 큐에 존재하는 작업이 일치할 경우 큐에서 삭제하고, 그렇지 않는 경우
다시 큐에 넣도록 하였다. 이 때 반복문의 반복 횟수는 기존 큐의 사이즈이다.

반복문을 다 돌고난 후 새로 들어온 작업을 큐에 추가한다. 마지막으로 큐를 뒤집어서 가장 최근
사용된 작업을 출력하여 문제를 해결한다.

강의에서는 메모리 사이즈의 크기만큼 배열을 생성하였다. 작업이 들어올 때 마다 배열을 순회하며
비교한다. 만약 동일한 작업이 존재하면 해당 요소의 인덱스를 저장하고, 다음 반복문에서 인덱스의
위치까지 배열 요소를 다음칸으로 옮기는 작업을 수행하여 문제를 해결한다.