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

LRU (Least Recently Used) 캐시 알고리즘

페이지를 교체할때 가장 오랫동안 사용되지 않은 페이지를 교체대상으로 삼는 것

캐시 공간이 부족할 때 사용하는 알고리즘 기법이라고 한다.

LRU에 대해서 처음들어보았고 이해를 다하지 못한 상태에서 문제를 풀었을때 계속해서 테스트케이스 4개정도가 실패하였다.

cache hit : 메모리가 캐시에 존재하는 경우
cache miss : 메모리가 캐시에 존재하지 않는 경우

여기서 놓치면 안되는 부분이 cache hit에서 메모리가 캐시에 존재하는 경우 result 값을 올려주는 동시에 존재하는 메모리를 맨 앞으로 옮겨주는 것이다. (이것때문에 계속 실패하였다,,)

이것만 이해한다면 어렵지않게 문제를 풀 수 있을 것이다.

function solution(cacheSize, cities) {
  var answer = 0;
  let cacheArr = [];
	
  if (cacheSize === 0) return 5 * cities.length;
  cities.map((city) => {
  
    let cityName = city.toLowerCase();

    if (cacheArr.includes(cityName)) {
      cacheArr.splice(cacheArr.indexOf(cityName), 1);
      cacheArr.unshift(cityName);
      answer += 1;
    } else {
      cacheArr.unshift(cityName);
      answer += 5;
      if (cacheArr.length > cacheSize) {
        cacheArr.pop();
      }
    }
  });

  return answer;
}