캐시

1. LRU는 가장 오랫동안 사용하지 않은 캐시값을 교체하는 방식이다
2. 캐시 미스는 새로운 값을 넣는 것이다
3. 캐시 힛은 기존에 있는 값을 넣는 것이다

구현하기

unshift가 생각나지 않아서 구현하는데 고생좀 했다

내가 짠 코드에는 두 개의 문제가 있었다

1. 처리할 데이터의 양이 캐시의 이하라면, 그 수만큼 캐시 미스가 난다고 가정했는데, 도시가 중복될 수 있으므로 무조건 그렇지 않다
2. 우연히 처리됐지만 캐시가 0인 경우 항상 캐시 미스가 난다
3. 문제의 조건대로 대소문자를 가리지 않아야하므로 도시의 이름을 대문자 또는 소문자로 통일할 필요가 있다

속도 비교

나의 코드

function sol00(cacheSize, cities) {
  let answer = 0;
  let cache = [];

  if (cacheSize === 0) {
    return 5 * cities.length;
  }

  for (let city of cities) {
    city = city.toLowerCase();
    const index = cache.indexOf(city);

    if (index !== -1) {
      answer += 1;
      cache.splice(index, 1);
    } else {
      answer += 5;
      if (cache.length >= cacheSize) {
        cache.pop();
      }
    }

    cache.unshift(city);
  }

  return answer;
}

다른 사람의 코드

function sol10(cacheSize, cities) {
  const MISS = 5, HIT = 1;

  if (cacheSize === 0) return MISS * cities.length;

  let answer = 0,
      cache = [];

  cities.forEach(city => {
      city = city.toUpperCase();

      let idx = cache.indexOf(city);

      if (idx > -1) {
          cache.splice(idx, 1);
          answer += HIT;
      } else {
          if (cache.length >= cacheSize) cache.shift();
          answer += MISS;
      }

      cache.push(city);
  });

나의 코드와 다를게 없다

function sol20(cacheSize, cities) {
  const map = new Map();
  const cacheHit = (city, map) => {
      map.delete(city);
      map.set(city, city);
      return 1;
  };
  const cacheMiss = (city, map, size) => {
      if(size === 0) return 5;
      (map.size === size) && map.delete(map.keys().next().value);
      map.set(city, city);
      return 5;
  };
  const getTimeCache = (city, map, size) => (map.has(city.toLocaleLowerCase()) ? cacheHit : cacheMiss)(city.toLocaleLowerCase(), map, size);
  return cities.map(city => getTimeCache(city.toLocaleLowerCase(), map, cacheSize)).reduce( (a, c) => a + c, 0);
}

return answer;
}

더 효율적인것같다

시간복잡도

sol00 : $O(N * C)$ 캐시의 길이 c 만큼 const index = cache.indexOf(city); 를 도시의 갯수 n만큼 한다
sol10 : $O(N * C)$ 캐시의 길이 c 만큼 const index = cache.indexOf(city); 를 도시의 갯수 n만큼 한다
sol20 : $O(N)$ 도시의 갯수 n만큼 $O(1) 짜리인 $map.delete(map.keys().next().value);

실행시간

도시의 길이에 따라서는 시간 복잡도만큼 증가했고, 캐시의 길이에 대해서는 최악의 경우까지는 증가하지 않았다.

배운 점

1. 시간 복잡도가 낮아도 기본 실행시간이 높으면 의미가 없다.

2. 시간 복잡도에 영향을 주는 인자가 여러개인 경우 변인 통제를 통해서 시간복잡도가 낮은것과 같은 효과를 낼 수 있다.