[ch7. 정렬과 그리디, 결정알고리즘(이분검색)] Least Recently Used(카카오 캐시 문제 변형) javascript

해당 포스팅은 인프런의 "자바스크립트 알고리즘 문제풀이" 강의 중 챕터7의 Least Recently Used 문제 풀이를 다룬다. 삽입정렬로 풀이하였다.

문제

풀이

처음에는 단순하게 자바스크립트 내장함수를 이용해서 풀었다.
하지만 해당 문제는 삽입정렬을 이용해서 배열의 원소들을 한 칸씩 뒤로 옮기고 원하는 위치에 값을 할당하라는 의도이다.

로직

• 캐시메모리 cache 생성 (size 크기만큼 배열 생성)
• nums를 loop돌리면서 각 원소들이 cache miss인지 hit인지 판별
  • cache hit인지 miss인지 확인하기 위해 캐시메모리인 cache에 현재 원소 x가 존재하는지 판별
  • 존재하면 cache hit, 존재하지 않으면 cache miss
• cache miss면 맨 앞에 현재 원소 x를 할당해주기 위해 idx 1~마지막 요소까지 한 칸 씩 뒤로 땡긴 후, idx 0에 x를 할당한다.
• cache hit이면 그 원소의 위치(pos) 이전 원소들을 전부 한 칸 씩 뒤로 땡기고, idx 0에 x를 할당한다.

삽입정렬 풀이

const size = 5;
const nums = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(size, nums));

function solution(size, nums) {
    const cache = [...Array(size)].fill(0);
    nums.forEach(x => {
        let pos = -1; // x 원소 위치 idx (x가 cache에 있는지 판별)
        for (let i=0; i<size; i++) {
            // 현재 작업이 cache에 존재 -> cache hit
            if (x === answer[i]) {
                pos = i;
            }
        }
        // cache miss
        if (pos === -1) {
            for (let i=size-1; i>=1; i--) {
                answer[i] = answer[i-1];
            }
        }
      	// cache hit
        else {
            for (let i=pos; i>=1; i--) {
                answer[i] = answer[i-1];
            }
        }
        answer[0] = x;
    })
    
    return nums;
}

자바스크립트 내장함수를 이용한 풀이

const s = 5;
const nums = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(s, nums));

function solution(s, nums) {
    const answer = [...Array(s)].fill(0);
    nums.forEach(n => {
        const idx = answer.indexOf(n);
        // 존재하지 않을 시 -> cache miss
        if (idx === -1) {
            answer.pop();
            answer.unshift(n);
        }
        // 존재할 시 -> cahce hit
        else {
            const sp = answer.splice(idx, 1);
            answer.unshift(...sp);
        }
    })
    return answer;
}