[Ch.06 - SortSearch] 04. LRU (Least Recently Used) 최근 최소 사용 알고리즘 ## (+ list.set, list.remove)

4. 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

 

 

---

 

import java.util.Scanner;

public class Main {
	public int[] solution(int n, int[] arr) {
		int[] answer = new int[n];
		// 캐시 히트, 캐시 미스 -> 위치를 -1로 지정후, pos으로 히트 유무 확인
		int pos = 0;
		for (int i = 0; i < arr.length; i++) {
			pos = -1;
			for (int j = 0; j < n; j++) {
				if (answer[j] == arr[i]) {
					pos = j;
					break;
				}
			}
			if (pos == -1) {
				for (int j = n-1; j > 0; j--) {
					answer[j]=answer[j-1];
				}
			} else {
				for (int j = pos; j > 0; j--) {
					answer[j]=answer[j-1];
				}
			}
			answer[0]=arr[i];
		}

		return answer;

	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[m];
		for (int i = 0; i < m; i++) {
			arr[i] = kb.nextInt();
		}

		for (int x : T.solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

 

+) 세련된 코드

import java.util.*;

public class Main {
	public int[] solution(int n, int m,int[] arr) {
		int[] answer= new int[n];
		for(int x:arr) {
			//캐시 히트와 캐시 미스 판단
			
			int pos=-1;
			//인덱스 번호
			for(int i=0;i<n;i++) if(x==answer[i]) pos=i;
			//히트면 인덱스 저장
			
			//미스면 -1;
			if(pos==-1) {
				for(int i=n-1;i>=1;i--) {
					//길이-1[마지막]부터 1까지 이동
					answer[i]=answer[i-1];
				}
				answer[0]=x;
				//현재 작업 0에 저장
			}
			else {
				for(int i=pos;i>=1;i--) {
					//히트부터 1까지 이동
					answer[i]=answer[i-1];
				}
				answer[0]=x;
				//현재 작업 0에 저장
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int[] arr = new int[9];
		for(int i=0;i<m;i++) {
			arr[i]=kb.nextInt();
		}
		for(int x:T.solution(n, m,arr))
			System.out.print(x+" ");
		
	}
}

 

 

---

ArrayList를 이용한 풀이

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> list = new ArrayList<>();
		int pos = 0, i;

		// 길이는 5고정
		for (int x : arr) {
			pos = -1;
			for (i = 0; i <list.size(); i++) {
				if (list.get(i) == x) {
					pos = i;
				}
			}

			if (pos == -1) {
				list.add(0,x);
			} else {
				list.remove(pos);
				list.add(0, x);
			}
		}

		while (list.size() != n) {
			for (int z = n; z < list.size(); z++) {
				list.remove(z);
			}
		}

		return list;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[m];
		for (int i = 0; i < m; i++) {
			arr[i] = kb.nextInt();
		}

		for (int x : T.solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

---

#List 메서드

 

set

list.set(위치, 숫자);

remove할 경우, 모든 '2' 삭제시

list.removeAll(Arrays.asList(2));

첫번째 2만 삭제시

list.remove(Integer.valueOf(2));

 

1.LIst 이용

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int s = in.nextInt();
    int n = in.nextInt();
    
 
    
    //1. List로 구현
    //set, add 두 가지
    List<Integer> list = new ArrayList<>();
    for(int i=0;i<n;i++){
      int x=in.nextInt();
      if(list.contains(x)){
        list.remove(Integer.valueOf(x));
        list.add(x);
      }else{
        if(list.size() <s){
          list.add(x);
        }
        else{
          list.remove(0);
          list.add(x);
        }
      }
     
    }
    for(int i=list.size()-1; i>=0; i--) System.out.print(list.get(i)+" ");
  }
}

 

2. 배열 이용

(1) 존재한다면

-> 존재하는 위치까지 모두 한칸씩 이동하고 0번째 칸에 해당 문자 삽입

(2) 존재하지 않는다면

-> 모두 한칸씩 이동하고 0번째 칸에 문자 삽입

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int s = in.nextInt();
    int n = in.nextInt();
    //작업 번호는 1부터 주어진다.
    //같은 번호가 존재하면 그 번호를 삭제하고 모두 한칸씩 이동
    //5칸 유지
    
    int[] answer= new int[s];
    e: for(int i=0;i<n;i++){
      int x=in.nextInt();
      for(int j=0;j<s;j++){
        if(answer[j]==x) {
           for(int k=j; k>0; k--){
            answer[k]=answer[k-1];
           }
          answer[0]=x;
          continue e;
        }
      }
      //j칸까지 모두 이동
      
      for(int k=s-1; k>0; k--){
        answer[k]=answer[k-1];
       }
      answer[0]=x;
      
      
    }
	for(int x1: answer) System.out.print(x1+" ");
  }
}