LRU 알고리즘 (Least Recentely Used)

프로그래머스 문제 풀다가 마주친 개념

LRU 알고리즘 (Least Recentely Used)

LRU 알고리즘은 페이지 교체 알고리즘이다. 즉, 페이지 부재가 발생했을 경우 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다.

LRU 알고리즘의 원리

정해진 캐시 크기를 초과했을 때 가장 오랫동안 참조되지 않은 페이지를 삭제하고 새로운 페이지를 추가한다.

LRU를 구현 시에는 Doubly Linked List 를 사용하는데,
Doubly Linked List => head ... tail
head 에 가까운 데이터일 수록 가장 최근에 사용한 데이터이고,
tail 에 가까운 node 일수록 가장 오랫동안 사용하지 않은 데이터이다.

문제 풀이

function solution(cacheSize, cities) {
    var answer = 0;
    let cacheArr = [];
    
    for (let city of cities) {
    const lowerCaseCity = city.toLowerCase()
     if(cacheArr.includes(lowerCaseCity)) {
         cacheArr = cacheArr.filter(city => city !== lowerCaseCity);
         cacheArr.push(lowerCaseCity);
         answer = answer+1
     } else {
         cacheArr.push(lowerCaseCity)
         answer = answer+5
     }
    if(cacheArr.length > cacheSize) {
            cacheArr.shift()
        }
    }
    return answer;
}

캐시에 존재하는 data라면 cache Hit이고, 존재하지 않으면 cache Miss이다.
cache Hit일 경우 기존의 데이터를 삭제하고, head에 새로 추가한다.
cache Miss일 경우 만약 캐시 사이즈보다 실제 사이즈가 작으면 그냥 추가하고,
캐시 사이즈를 초과하게 된다면 가장 오래된 데이터(tail)를 삭제하고 새로 추가한다.