[큐] 캐시

[ericagong]

⭐ 성찰

1. Array.prorotype.slice(start, end) vs Array.prototype.splice(start, deleteCount, item1, item2, itemN) 차이
2. Array.prorotype.find(func), Array.prototype.findIndex(func) vs Array.prototype.indexOf(value) va Array.prototype.includes(searchElement, fromIdx) 차이

❓ 문제 상황

캐시

👨‍💻 문제 해결: 큐 통한 FIFO

✅ 1차 풀이: 큐를 통해 LRU 구현

⭐ 예외처리 ⭐ cacheSize가 0인 경우도 들어올 수 있음

1. cache hit인 경우, 배열 내 존재여부를 Array.prototype.indexOf(값)으로 확인하고, 존재 시 기존 배열 내에서 해당 값을 Array.prorotype.splice(idx, 1)으로 삭제.
2. cache miss인 경우, 배열의 길이가 cacheSize 넘는 경우만 Array.prorotype.shift()로 가장 오래된 도시 이름을 제외.
3. cache hit/miss에 상관없이 배열에 신규 도시명을 추가.

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

  // cacheSize 0인 경우, 예외 처리
  if (cacheSize === 0) return MISS * cities.length;

  let answer = 0;
  let cache = [];

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

    // cache hit 여부 확인
    let idx = cache.indexOf(city);

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

    cache.push(city);
  });

  return answer;
}

✅ 2차 풀이: 시간복잡도를 고려해 Map으로 해결

1. cache 내 존재 시, cache hit 처리 + 기존 요소 삭제 후 신규 요소 추가
2. cache 내 미존재시, cache miss 처리
   • cache가 full이면, LRU 처리 -> 기존 가장 오래된 요소 삭제, 신규 요소 추가
   • cache full 아니면, 신규 요소 추가만.

function solution(cacheSize, cities) {
    if(cacheSize === 0) return cities.length * 5

    cities = cities.map((city) => city.toLowerCase())

    let time = 0
    const cache = new Map()

    cities.forEach((city, t) => {
        if(cache.has(city)) {
            time += 1
            cache.delete(city)
            cache.set(city, t)
        }
        else {
            time += 5
            if(cache.size === cacheSize) {
                const target = cache.keys().next().value
                cache.delete(target)
            }
            cache.set(city, t)
        }
    })

    return time
}

[ericagong]

리뷰 완료 👍