[프로그래머스] [1차] 캐시 (JS)

풀이 과정

1. 캐시 배열 생성
2. 각 도시에 대해 반복
3. 현재 도시가 캐시 배열에 있는지 확인해서 있으면 결과 +1, 아니면 +5
   이때 캐시에 있으면 삭제
4. 캐시 배열에 현재 도시 넣기: push()
5. 캐시 사이즈를 넘었으면 0번째 인덱스 삭제: slice()

코드

function solution(cacheSize, cities) {
  let cache = [];
  let result = 0;
  for (const city of cities) {
    const i = cache.indexOf(city.toLowerCase());
    result += i >= 0 ? 1 : 5;
    if (i >= 0) cache = [...cache.slice(0, i), ...cache.slice(i + 1)];
    cache.push(city.toLowerCase());
    if (cache.length > cacheSize) cache = cache.slice(1);
  }
  return result;
}

🦾

처음에 왜이리 쉽지 하고 풀었더니 통과하지 못하는 케이스가 있었다.
LRU 알고리즘이 뭔지 제대로 모르고 풀어서였다.
매번 그냥 오래된 거 지우고 새로운 거 붙이는 방식으로 풀었는데, 이게 아니라 캐시에 찾는 요소가 이미 있으면 지운 다음에 새로 붙여야 했다.
무튼 이중 연결 리스트로 head, tail을 가지지는 않아서 제대로 LRU 알고리즘을 구현했다기 보다는 약식인 듯

LRU 알고리즘

Least Recently Used

• 페이지 교체 알고리즘의 한 종류로, 가장 오랫동안 참조되지 않은 페이지를 삭제하는 방식
• 가장 최근에 사용한 페이지 순서로 정렬되어 있어 접근 속도가 빠름
• 이중 연결 리스트로 구현되며 head와 tail을 가짐
• head는 최근에 참조한 페이지를 가리킴
• cache hit인 경우 현재 위치에서 노드를 삭제하고 head 다음에 삽입
• cache miss인 경우 head 다음에 삽입
• 캐시 크기를 초과하면 tail 이전의 노드를 삭제