코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)
LRU(Least Recently Used)
5_hyun
2022. 12. 5. 23:29
반응형
LRU
해결 방법
해결 방법으로는 내장 함수를 사용하지 않는 방법과 내장 함수를 사용하는 방법 2가지가 있다.
나는 이 문제를 처음 풀 때 꼼수를 사용하여 맨 뒤부터 불러오는 방식으로 풀려고 했지만 이 방식은 옳은 방법이 아니였다.
방법1) 내장 함수를 사용하지 않는 방법
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
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 (answer[i] === x) 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));
</script>
</body>
</html>1. pos는 히트가 되었는지 안되었는지 확인할 수 있는 변수이다. 만약 pos가 -1이면 히트가 되지 않은 것, pos가 -1이 아니면 히트가 된 것이고 pos에 히트 된 위치를 저장한다.
2. pos가 -1이면 히트가 되지 않았기 때문에 answer에 들어간 모든 값들을 뒤로 한 칸씩 밀어주고 맨 앞에 현재 값을 넣는다.
3. pos가 -1이 아니면 히트가 되었기 때문에 히트 된 앞 부분부터 뒤로 한 칸씩 밀어주고 맨 앞에 현재 값을 넣는다.
방법2) 내장 함수를 사용하는 방법
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
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 (answer[i] === x) pos = i;
if (pos === -1) {
answer.unshift(x);
if (answer.length > size) answer.pop();
} else {
answer.splice(pos);
answer.unshift(x);
}
});
return answer;
}
let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr));
</script>
</body>
</html>이 방법도 기본은 방법1과 유사하다.
1. pos로 히트가 되었는지 안되었는지 찾는 부분은 똑같다.
2. 만약 pos가 -1이라 히트되지 않았다면 unshift를 통해 answer의 맨 앞에 넣어준다. 만약 answer의 길이가 size보다 커지면 pop을 하여 개수를 유지해준다.
3. 만약 pos가 -1로 히트되었다면 splice를 통해 히트된 위치의 값을 제거해주고 맨 앞에 현재 사용된 값을 넣어준다.
반응형