LRU(Least Recent Used)

frenchkebab·2021년 8월 27일

javascript 알고리즘 - 정렬

목록 보기

5/6

내풀이

내풀이1 - 내장함수로 구현

function solution(size, arr) {
  let cache = Array.from({ length: size });
  let answer = cache;
  for (let x of arr) {
    // cache hit
    let idx = cache.indexOf(x);
    if (idx > -1) {
      x = cache[idx];
      cache.splice(idx, 1);
    } else cache.pop();
    cache.unshift(x);
    console.log(cache);
  }
  return answer;
}

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

내풀이2 - 내장함수 없이 구현

function solution(size, arr) {
  let cache = Array.from({ length: size });
  let answer = cache;

  for (let x of arr) {
    let pos = -1;
    // hit인지 miss인지 판별
    for (let i = 0; i < cache.length; i++) if (cache[i] === x) pos = i;
    // hit인 경우
    if (pos > -1) {
      x = cache[pos];
      for (let j = pos - 1; j >= 0; j--) {
        cache[j + 1] = cache[j];
      }
      // miss인 경우
    } else {
      for (let j = cache.length - 2; j >= 0; j--) {
        cache[j + 1] = cache[j];
      }
    }
    cache[0] = x;
    console.log(cache);
  }
  return answer;
}

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

Solution 풀이

Solution 풀이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));

내장함수로 풀었는데 왜 또 includes 혹은 indexOf 함수는 사용하지

Solution 풀이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));