[프로그래머스][JS]캐시

문제

문제: https://programmers.co.kr/learn/courses/30/lessons/17680

이번 문제는 코드 구현보다 문제를 이해하는데 시간을 더 쓴것같다.

cache hit, cache miss 가 도대체 무엇일까?
캐시알고리즘 LRU(Least Recently Used)란? 무엇일까?

그래서 LRU(Least Recently Used)를 간단하게 소개하자면

LRU(Least Recently Used)

캐시에서 가장 사용한지 오래된 캐시를 지우는 알고리즘

즉, 캐시크기가 꽉 찼고 새로운 값을 캐시에 넣을 때, 캐시 내에서 사용한지 가장 오래된 값을 지우고 새로운 값을 캐시에 넣는다.

위의 LRU의 내용을 이해한다면 문제를 이해할 수 있게 됩니다.

cache hit: 캐시안에 현재 값이 들어있기 때문에 +1
cache miss: 캐시안에 현재 값이 없기 때문에 +5

해결방법

• 캐시 교체 알고리즘이 LRU이기 때문에 사용한 값은 캐시배열 맨 뒤에 넣어줄 것입니다.
• 캐시 크기가 0일 경우는 캐시가 없으므로 모든 값이 cache miss이기 때문에 따로 처리해줬습니다.

1. 캐시 배열을 만들어준다. 이곳에 데이터가 들어가서 캐시체크를 해줄겁니다.

2. cities 안에 맨 앞에 값(city)을 빼서 cache배열 안에 있는지 체크 합니다.

   2-1. 있는 경우: cache배열에서 city값을 지워주고, 맨 뒤에 city값을 push해줍니다. 그리고 answer+=5

   • 캐시가 사용되면 가장 최근에 사용한 값이 되므로 맨 뒤에 넣어주기 위해서 삭제를 하고 push 해주는 것입니다

   2-2. 없는 경우: cache배열에서 맨 앞의 값(사용한지 가장 오래된 값)을 제거(shift())하고 맨 뒤에 city값을 push해줍니다. 그리고 answer+=1

위의 과정만 하면 끝입니다. 캐시에 대해 조금이라도 알고 있었다면 간단한 문제인것 같습니다.

code

function solution(cacheSize, cities) {
  var answer = 0;
  let cache = [];
  //캐시 크기가 0인 경우는 따로 처리
  if (cacheSize === 0) return cities.length * 5;

  while (cities.length) {
    const city = cities.shift().toLowerCase();
    if (cache.includes(city)) {
      cache.splice(cache.indexOf(city), 1);
      cache.push(city);
      answer += 1;
    } else {
      if (cache.length === cacheSize) {
        cache.shift();
      }
      cache.push(city);
      answer += 5;
    }
  }
  return answer;
}

마무리

카카오 문제를 풀기 위해서는 기본적인 cs지식도 요구된다는 것을 알게됐습니다. 아직 cs공부를 많이 못했지만 앞으로 꾸준히 준비해 나가면 될 것 같다는 생각이 듭니다.