[Algorithm] [1차] 캐시

문제 설명

[1차] 캐시는 캐시에 저장 가능한 크기만큼 도시들을 후입선출하고 캐시에 이미 같은 도시가 존재하는 경우 +5, 존재하지 않는 경우 +1을 실행시간에 더하여 총 실행시간을 반환하는 문제로 LRU 알고리즘을 요구한다.

LRU 알고리즘

운영체제의 페이지 교체 알고리즘 중 하나이며 캐시의 제한된 용량에서 제일 오랫동안 참조되지 않은 페이지를 교체하는 방법이다.

• Cache Hit

  참조하고자 하는 데이터가 캐시에 존재하는 경우

• Cache Miss

  참조하고자 하는 데이터가 캐시에 존재하지 않는 경우

문제 해결

입력받은 배열을 순회하며 도시들을 소문자로 변환하여 캐시 배열에 저장한다.
저장하고자 하는 도시가 캐시 배열에 이미 존재하는 경우 참조된 도시를 제거하고 새로 추가한 후 실행시간에 1을 더한다.
존재하지 않는 경우 실행시간에 5를 더하고 입력받은 캐시의 크기보다 캐시 배열의 크기가 커질 경우
캐시 배열의 0번쩨 인덱스의 도시를 제거한다.

function solution(cacheSize, cities) {
    let cache = [];
    let playTime = 0;
    
    for (let i = 0 ; i < cities.length; i++) {
        const currentCity = cities[i].toLowerCase();
        let findCity = cache.find(city => currentCity === city);
        if (!findCity) {
            cache.push(currentCity);
            if (cache.length > cacheSize) {
                cache.shift(currentCity);
            }
            playTime+=5;
        } else {
            cache = cache.filter(city => city !== currentCity);
            cache.push(currentCity);
            playTime+=1;
         }
    }
    return playTime;
}