[programmers] 캐시 (in JS)

문제

캐시-2018 kakao blind recruitment

• 캐시 크기와 도시 이름 배열을 입력받는다.
• 도시 이름은 영문자로 구성되며, 대소문자를 구분하지 않는다.
• 캐시 교체 알고리즘은 LRU를 사용한다.
• cache hit은 실행시간 1이고, cache miss는 실행시간 5이다.
• 도시 이름 배열을 순서대로 처리할 때, '총 실행시간'을 출력한다.

Fact

• 도시 이름은 대소문자를 구분하지 않으므로, 대문자나 소문자로 고정하여 캐쉬에 저장하여야 한다.
• 캐시 크기가 0이면 어떠한 도시라도 캐시 미스가 발생한다.
• 캐시에 도시가 다 채워져있을 때, 캐시 미스가 발생하면 가장 오랫동안 사용이 안된 도시를 캐시에서 지워야 한다.
• 가장 최근에 사용된 도시는 캐시의 맨 뒤에 저장한다면, 캐시의 첫 번째는 가장 오랫동안 사용되지 않은 도시이다. 이 도시가 캐시 미스가 되었을 때 교체 대상이 된다.

접근

도시는 대소문자를 구분하지 않으므로, 입력받은 도시이름 배열에서 모든 도시를 소문자로 변환한다.

가장 최근에 사용된 도시는 캐시의 맨 뒤에 저장하도록 하였다.
맨 앞에 있는 도시는 캐시 미스시 교체 대상이 되는 도시이다.

도시가 캐시에 있다면, 캐시에 있는 도시는 가장 최근에 사용된 것이므로, 위치를 캐시의 맨 뒤로 옮긴다.

도시가 캐시에 없을 땐, 캐쉬의 맨 뒤에 도시를 추가해야 한다. 그 전에, 캐시에 있는 도시의 수가 캐시 크기를 이상인지 확인해야 한다. 도시의 수가 캐시 크기 이상이라면, 캐시에서 가장 앞에 있는 도시를 삭제한다. 그 후, 캐쉬의 맨 뒤에 도시를 추가한다.

복잡도

• 공간 복잡도 : O(k), k는 0이상 30이하
• 시간 복잡도 : O(N)
  • 도시이름 배열을 처음부터 끝까지 순회한다.

알게된 점

• 배열의 첫 번째 요소를 삭제하는 메서드는 Array.prototype.shift()이다.이 메서드는 기존 배열을 변형한다.
• 배열의 앞에 요소를 추가하는 Array.prototype.unshift()이다. 이 메서드 또한 기존 배열을 변형한다.

코드

const HIT = 1;
const MISS = 5;

const isInCache = (cityList, target) =>
  cityList.some((city) => city === target);

const removeFromCache = (cityList, target) =>
  cityList.filter((city) => city !== target);

function solution(cacheSize, cities) {
  if (cacheSize === 0) {
    return cities.length * MISS;
  }
  const lowCities = cities.map((city) => city.toLowerCase());
  let cache = [];
  const totalTime = lowCities.reduce((time, city) => {
    if (isInCache(cache, city)) {
      cache = [...removeFromCache(cache, city), city];
      return time + HIT;
    }
    if (cache.length >= cacheSize) {
      cache.shift();
    }
    cache.push(city);
    return time + MISS;
  }, 0);
  return totalTime;
}