[JavaScript/section 7] 05 - LRU

📌 05 - Least Recently Used(카카오 캐시 문제 변형)

만약 캐시의 사이즈가 5이고 작업이 [2, 3,  1, 6, 7] 순으로 저장되어 있다고 가정해보자❗

1) Cache Miss: 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작업을 CPU가 사용한다면  Cache Miss가 되고 모든 작업이 뒤로 밀린 후 5번 작업은 캐시의 맨 앞에 위치한다. [5, 2, 3, 1, 6] (7번 작업은 캐시에서 삭제된다.)

2) Cache Hit: 해야할 작업이 캐시에 있는 상태로  위 상태에서 만약 3번 작업을 CPU가 사용한다면 Cache Hit이 되고, 3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀린 후 3번 작업은 캐시의 맨 앞에 위치한다. [3, 5, 2, 1, 6]

나의 풀이 방법

이 직전에 풀었던 삽입 정렬 문제의 풀이 방법을 이용해 풀었다. 

• for 문을 돌면서 tmp 변수에 배열의 자료를 하나씩 저장한다.
• tmp가 캐시에 있는 상태인지 아닌지를 includes() 함수를 이용해 판단한다.
• Cache Hit일 경우 indexOf() 함수를 이용해 tmp가 캐시에서 위치한 곳을 찾는다.
• 위치한 곳 앞에 있는 작업은 한 칸 뒤로 밀리고, 해당 작업은 캐시의 맨 앞에 위치한다.
• Cache Miss일 경우 모든 작업이 뒤로 밀리고, 해당 작업은 캐시의 맨 앞에 위치한다.

👍 강사님 풀이 방법

강사님은 삽입 정렬과 JS의 내장 함수를 이용하여 문제를 푸셨다. 삽입 정렬을 이용한 방법의 경우 나의 풀이 방법과 유사하므로 내장 함수를 이용한 방법에 대해서 써보려고 한다. 본인에게 편한 방법으로 풀면 된다.

• for 문을 돌면서 작업이 캐시에 있는 상태인지 아닌지를 판단함과 동시에 캐시에서 위치한 곳(pos)을 찾아 저장한다.
• Cache Miss일 경우 unshift() 함수를 이용해 배열의 맨 앞에 작업을 추가한다. 추가한 후 배열의 길이가 주어진 size를 안넘도록 한다.
• Cache Hit일 경우 slice(pos, 1) 함수를 이용해 해당 작업을 캐시에서 제거한 후 캐시의 맨 앞에 위치하도록 한다.

 

📝 풀이

// 나의 풀이 방법
function solution(size, arr) {
  let answer = Array.from({ length: size }, () => 0);

  arr.forEach((data) => {
    let tmp = data;
    let i;

    // Cashe Hit
    if (answer.includes(tmp)) {
      let index = answer.indexOf(tmp);
      // 해당 작업 앞에 있는 작업은 한 칸 뒤로 밀리고, 해당 작업은 캐시의 맨 앞에 위치
      for (i = index - 1; i >= 0; i--) {
        answer[i + 1] = answer[i];
      }
    }
    // Cashe Miss
    else {
      // 모든 작업이 뒤로 밀리고, 해당 작업은 캐시의 맨 앞에 위치
      for (i = size - 2; i >= 0; i--) {
        answer[i + 1] = answer[i];
      }
    }
    answer[i + 1] = tmp;
  });

  return answer;
}

let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr));

// 강사님 풀이 방법1(삽입 정렬 응용)
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));

// 강사님 풀이 방법2(내장 함수 사용)

function solution(size, arr) {
  let answer = [];

  arr.forEach((x) => {
    let pos = -1;
    for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;
    if (pos === -1) {
      answer.unshift(x);
      if (answer.length > size) answer.pop();
    } else {
      answer.splice(pos, 1);
      answer.unshift(x);
    }
  });

  return answer;
}

let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr));