[정렬] Least Recently Used

 

 

 

설명

 

 

 

 

 

 

 

풀이

 

자료구조는 int 배열을 사용하며 알고리즘은 정렬을 활용한다.

 

 

로직은 다음과 같다.

• 캐시 크기만큼의 int 배열을 생성한다.
• 작업이 들어있는 배열을 돈다.
  • 초기 int형 변수 pos를 -1로 둔다. 이 변수는 현재 수가 캐시에 존재하는지 확인할 수 있는 변수이다.
  • 캐시 배열을 돌면서 현재 수가 캐시 배열에 존재하는지 확인한다.
    • 존재한다면 해당 인덱스 변호를 pos 변수에 저장한다.
  • pos가 -1 이면 캐시에 현재 값이 존재하지 않는다는 뜻이다. 즉, miss 인 경우이다.
    • 배열의 맨 뒤부터 1번 인덱스까지 1 감소시키며 반복문을 돈다.
      • 오른쪽으로 수를 하나씩 민다. 캐시 배열의 i-1 번째 인덱스의 값을 캐시 배열의 i 번째 인덱스의 값에 넣는다.
  • pos가 -1이 아니면 캐시에 현재 값이 존재한다는 뜻이다. 즉, hit 인 경우이다.
    • pos 부터 1번 인덱스까지 1 감소시키며 반복문을 돈다.
      • 오른쪽으로 수를 하나씩 민다. 캐시 배열의 i-1 번째 인덱스의 값을 캐시 배열의 i 번째 인덱스의 값에 넣는다.
  • 캐시의 맨 0번째 값에 현재 값을 넣는다.
• 캐시 배열을 리턴한다.

 

 

 

 

코드

package inflearn._6_4;

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

/**
 * 삽입 정렬로 구현하기
 */
public class Main {

    public static int [] solution(int s, int n, int [] arr) {

        int [] cache = new int[s]; // 캐시

        // 작업이 들어있는 배열 돌면서
        for(int x : arr) {

            int pos = -1;

            // x 가 cache 에 존재하는지 확인
            // 이 과정으로 pos가 정해짐 (pos로 miss(원소가 캐시에 존재하지 않음)인지 hit(원소가 캐시에 존재함)인지 알 수 있음)
            for(int i = 0; i < s; i++) {
                if (x == cache[i]) pos = i;
            }

            // miss (캐시에 현재 값이 존재하지 않음)
            if (pos == -1) {
                for(int i = s-1; i >= 1; i--) { // 맨 뒤부터
                    cache[i] = cache[i-1]; // 오른쪽으로 한 칸씩 당기기
                }
            }

            // hit (캐시에 현재 값이 존재함)
            else {
                for(int i = pos; i >= 1; i--) { // hit된 그 인덱스부터
                    cache[i] = cache[i-1]; // 오른쪽으로 한 칸씩 당기기
                }
            }

            cache[0] = x; // 캐시의 맨 첫번째에 현재 값 넣기

        }

        return cache;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int s = Integer.parseInt(st.nextToken()); // 캐시 사이즈
        int n = Integer.parseInt(st.nextToken()); // 작업 개수

        st = new StringTokenizer(br.readLine(), " ");

        int [] arr = new int[n]; // 작업이 저장되어 있는 배열

        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int [] cache = solution(s, n, arr);

        for(int x : cache) {
            sb.append(x).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();

    }
}