Programmers / Level 2 / [1차] 캐시 / JS

< 문제 바로가기 >

프로그래머스

 

function solution(cacheSize, cities) {
  let cache = [];
  const [HIT, MISS] = [1, 5];
  let answer = 0;

  cities = cities.map(el => el.toLowerCase());

  for(const CITY of cities) {
    // 캐시에 이미 있다면
    if(cache.includes(CITY)) {
      answer += HIT;
      cache.splice(cache.indexOf(CITY), 1);
    }
    // 캐시에 없다면
    else answer += MISS;

    cache.push(CITY);

    // 캐시 사이즈가 넘어간다면 맨 앞 삭제
    if(cache.length > cacheSize) cache.shift();
  }

  return answer;
}

---

이 풀이대로 하면 시간초과가 날 것 같았는데 안나는 의외의 풀이였다.

LRU 알고리즘이란 Least Recently Used의 약자로 직역 그대로 가장 최근에 사용되지 않은, 즉 가장 오래된 것을 삭제하는 알고리즘이다.

 

위 코드대로 하면 캐시에 이미 있는 값이라면, 배열에서 삭제해주고 다시 맨 뒤에 push 해주면 된다.

만약 캐시에 없다면 MISS 값만 더해주고 뒤에 push 해준다.

 

가장 최신에 들어온 것은 배열의 맨 마지막에 위치하게 된다.

따라서 가장 오래된 것은 맨 앞의 요소이다.

 

그러므로 사이즈를 넘어가면 단순히 맨 앞에서 shift() 해주면 된다.