이전 소개한 LRU Cache를 삽입 정렬식으로 구현했다.
가장 최근에 사용한 데이터가 맨 앞의 저장 공간에 자리를 차지하고
가장 나중에 사용한 데이터가 뒤로 가는 구조이다.
이때 기존에 정해진 캐시 사이즈를 넘어가게 되면(overflow)
가장 뒤에 있는 데이터가 밀려나서 삭제되는 식의 자료구조이다.
역시나 알고리즘 자체를 이해하는 것과 실제 적용하는건 천지차이다.
문제 설명을 하자면,
캐시 사이즈를 5로 정하고
그 이후 하나씩 입력을 받아 밀려나가면서 최종 캐시의 데이터를 보여주면 된다.
function solution(size, arr) {
let answer = Array.from({ length: size }, () => 0);
arr.forEach((x) => {
let pos = -1;
for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;
if (pos === -1) {
for (let i = size - 1; i >= 1; i--) {
answer[i] = answer[i - 1];
}
} else {
for (let i = pos; i >= 1; i--) {
answer[i] = answer[i - 1];
}
}
answer[0] = x;
});
return answer;
}
let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr));코드는 이러하다.
의미없는 코드가 없다는걸 다시 한번 생각하며 코드 설명에 들어가겠다.
let answer = Array.from({ length: size }, () => 0);
첫 줄 answer에 캐시 데이터를 담을 공간을 마련한 것이다.
이 상황에선 answer가 즉 캐시가 된다.
Array.from({ length: size }, () => 0); 의 결과는 [0,0,0,0,0] 이 된다.
size = 5 를
()=> 0 으로 초기화
arr.forEach((x) => {
let pos = -1;
for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;
forEach문 역시 for of 처럼 arr 배열을 하나씩 순회하는것 그 이상 그 이하도 아니다.
안의 let pos = -1 은 일단 pos 초기값이 -1 이라는 것만 알아두고 넘어가자.
for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;
이 코드에서 for 문과 if문 모두 단문으로 줄인것이 가장 먼저 눈에 들어와야한다.
i를 size = 5 보다 작을 때 까지 돌리고
그 안에서 if 문을 작성한 셈이 되는 것이다.
if (x === answer[i])
x는 arr를 돌고 있는 친구이고 , 그 값이랑 answer[i] i 역시 돌고 있는 친구의 값이
일치한다면 pos = i // 처음 -1로 선언했던 pos의 값이 i가 되는 것이다.
여기서 중요한건 만약 일치하지 않는다면 ?
처음 선언한 -1 의 값이 그대로 pos 에 남아있을 것 이다.
if (pos === -1) {
for (let i = size - 1; i >= 1; i--) {
answer[i] = answer[i - 1];
}
}
이어서 pos가 -1 이라면의 if문이 등장한다.
위에서 설명한거처럼 pos가 -1 이라면 그 위의 조건이 false기 때문에
초기에 설정한 값이 그대로 유지된것이다.
for (let i = size - 1; i >= 1; i--) {
answer[i] = answer[i - 1];
}
}
그랬을 때 i는 size -1 (4) 부터 1이랑 같아질때까지 --하면서 for문을 돈다.
answer[i] = answer[i - 1]; 이 코드를 잘 봐야하는데이때 캐시의 구조를 떠올릴 필요가 있다.
answer[i] 는 현재 answer[4] 즉 캐시의 맨 마지막이다.
answer[i-1] 는 현재 answer[3] 즉 캐시의 마지막보다 한칸 앞이다.
한칸 앞에 있는 데이터를 맨 마지막으로 넘겨주는거다.
그럼 자연스럽게 맨 마지막에 있는 데이터는 지워지는 것이다.
꼭 지워져야한다. 어디에 그 값이 남아있거나 캐시의 크기가 커지는게 아니다.
else {
for (let i = pos; i >= 1; i--) {
answer[i] = answer[i - 1];
}
}
여기서 else는 pos의 값이 -1 이 아니고 어떠한 값이 맨 위의 pos = i 코드로 인해
어떤 값이 채워졌을 경우를 말하는 것이다.
참고로 어떤 값이 채워져? 라고 할 수 있는데
초기에 순회한 배열을 보면 같은 값이 들어가있는 경우를 볼 수 있다.
딱 그 경우를 말하는 것이다.
다른 값을 만나면 가장 처음으로 넣어주기만 하면 되는데
기존 캐시에 있는 값을 만났을 땐 ?
당연히 그 값도 맨 처음으로 넣어줘야한다.
단, 중복되는 값을 그대로 두는게 아니라 밀려나야한다.
캐시의 구조상 오래된 값이 밀리는데 그 자리에 그대로 두면
가장 최근에 사용했는데도 불구하고 삭제될 것을 방지하는 것이다.
for (let i = pos; i >= 1; i--) {
answer[i] = answer[i - 1];
같은 값을 만나게 되면
그 자리부터 하나씩 밀리는 것이다.(기존 값을 삭제시키고 새로 추가)
answer[0] = x;
이 코드가 새로 추가하는 코드이다.
answer[0] 가장 처음의 자리에 x를 넣어준다.
주의할 점 :
스코프를 잘 보면서 읽어야한다.
항상 마찬가지지만 인덱스 숫자와 값의 숫자를 잘 구분해서 봐야한다.
결국 캐시의 구조를 구현하고자 함으로 캐시의 성질을 생각하면서 해결해야한다.
추가적으로 unshift와 pop 메서드를 사용해 더 간단하게 구현도 가능하다.
