[프로그래머스/JavaScript] [1차] 캐시

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

---

1) 풀이

2018 KAKAO BLIND RECRUITMENT 라고 해서 쫄았는데, 생각보다 간단했던 문제!

이 문제를 풀기 위해서 캐시 교체 알고리즘인 LRU(Least Recently Used)에 대해서 알아야 한다!

내가 참고한 블로그에 대해서는 링크를 걸어놨으니 그 내용은 따로 담지 않겠다

 

cacheSize만큼 담을 수 있는 캐시(cache)라는 배열을 만들어놓고, 그 배열을 확인한 뒤 현재 요소가 들어있으면 hit, 없으면 miss의 로직을 진행하면 되는 문제였다

적절하게 실행시간을 더해주고, 알고리즘에 맞게 캐시를 교체해주는 작업을 수행했는데 채점을 해보니 7번, 17번만 틀렸다고 나왔다. 이유를 도저히 모르겠어서 '질문하기' 란을 확인해보니, cacheSize=0 일때를 고려하지 못했다는 것을 알았다!

cacheSize가 0일때는 무조건 실행시간을 5로 더하고 cache 배열에 아무것도 넣지 않아야 하므로 따로 예외처리를 해주어야한다. 그렇게 하면 정답!

2) 최종 소스코드

function solution(cacheSize, cities) {
    const cache=[];
    let chkHit=0;
    let answer = 0;
    for(let i=0;i<cities.length;i++){
            cities[i]=cities[i].toLowerCase();
            chkHit=cache.findIndex(v=>v===cities[i]);
            if(cacheSize===0) {
                answer+=5;
                continue;
            }
            if(chkHit===-1){//cache miss
                answer+=5;
                if(cache.length<cacheSize) cache.push(cities[i]);
                else{
                cache.shift();
                cache.push(cities[i]);
                }
            }else{ //cache hit
                answer+=1;
                cache.splice(chkHit,1);
                cache.push(cities[i]);
            }
    }
    return answer;
}

3) 참고자료

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)