[프로그래머스] 1차 캐시 - 자바스크립트

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

코딩테스트 연습 - [1차] 캐시

 

문제의 난이도보다, 문제 풀이에 나왔던 조건들 때문에, 글을 남긴다.

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

 

cache hit, 과 cache miss는 테트 케이스를 연산해보면, 어떤 의미인지 알 수 있다. 최대 저장량 cache에 값이 존재한다면, cache hit, 없다면 cache miss, 그래서 stack 으로 구현을 해서 값이 겹치면, 1, 없다면 5를 넣고 계산을 했는데, 테스트케이스는 통과했지만, 나머지 케이스를 절반만 맞을 수 있었다. 그래서, LRU가 어떤건지 검색을 하며(사실 stack을 원래 알던 cache대로 했다면 아마 맞았을꺼같다..) LRU는, 메모리가 3이라고 할 때는, 메모리에 3개의 값만 들어가고, 최근에 값이 들어간 순으로 없앤다. 여기서의 USED는, update, create라고 생각하면 될꺼같다. 그리고, 21111111112 순으로 들어갔을때는 21 ->21 -> 21(같은 1이들어가면 업데이트만 된다) -> 12로 바뀔 수 있게, 수정했다. 그냥 단순히 push shift로만  구현하면 21 -> 1 -> 12가 되기에 구현이 이상하게 되기 때문이다.

function solution(cacheSize, cities) {
    var answer = 0;
    let stack = [];
    for(let i =0; i<cities.length;i++){
        cities[i] = cities[i].toUpperCase();
        if(stack.includes(cities[i])){       
            const ele = stack.indexOf(cities[i])
            answer = 1 + answer
            stack = [...stack.slice(0, ele), ...stack.slice(ele+1)];
            stack.push(cities[i])
        }else{

                stack.push(cities[i])
                if(stack.length>cacheSize){
                stack.shift()
                }
                answer = 5 +answer

        }

    }
    return answer;
}