Lease Recently Used(삽입정렬 활용)

문제

나의풀이

import java.util.*;
class Main {
	public int[] solution(int s,int n,int[] arr) {
		int[] cache = new int[s];
		for(int x : arr) {
			int pos = -1;
			//hit or not
			for(int i=0;i<s;i++) if(x == cache[i]) pos = i;
			//miss
			if(pos==-1) {
				for(int i=s-1; i>0;i--) {
					cache[i] = cache[i-1];
				}
			}
			//hit
			else {
				for(int i=pos;i>0;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 + " ");
	}
	
}

풀이방법

1. arr에서 들어오는 값은 항상 cache의 맨 앞에 꽂힌다.
2. 만약 cache hit가 발생하면 해당값은 사라진다.
3. hit가 발생하지 않는다면 모두 miss이므로 한 칸씩 다음칸으로 미뤄진다.

스스로 풀지 못하고 강의를 듣고 풀었다...

먼저, arr값을 순서대로 받을 foreach문을 만들고,
hit 발생여부를 확인할 pos를 만든다.

cache배열 탐색을 통해 만약 hit가 발생하면 발생한 지점의 인덱스를 pos에 저장한다.

hit가 발생하지 않았다면 pos는 그대로 -1이다.(miss)

pos=-1이라면 cache배열의 모든값을 한칸씩 앞에서 땡겨온다.(삽입정렬)
그리고 마지막으로 맨 처음값에 x값을 넣어준다.

hit가 발생했다면, hit가 발생한 지점부터 값을 한칸씩 땡겨온다.
마찬가지로 맨 처음값에 x값을 넣어준다.

핵심키워드

pos=-1로 지정해두고 같은값이 배열에 있다면 해당 위치index를 저장하는 방법을 기억해두고 유용하게 사용하자!