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

프로그래머스

---

문제 조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

---

cache hit 은 캐시에 요청한 데이터가 존재하는 경우이다.
cache miss 는 캐시에 요청한 데이터가 존재하지 않는 경우이다.
LRU는 캐시 공간이 부족할 경우 캐시에서 가장 오랫동안 사용되지 않은 데이터를 삭제하는 방식이다.

풀이

캐시 사이즈가 0인 경우, 

if(cacheSize === 0) return cities.length * 5;

모든 요소들이 cache miss 일 것이기 때문에 위와 같이 배열 길이에 5를 곱한 값을 반환해준다.

그 외에 cacheSize가 1 이상인 경우에 대해 구해보자.

cities = cities.map(x => x.toLowerCase());

도시 이름의 대소문자를 구분하지 않으므로 위와 같이 cities의 모든 요소들을 toLowerCase로 소문자로 변경해준다.

같은 이름의 도시가 대소문자 구분에 의해 다른 도시로 인식되지 않도록 하기 위함이다.

이제 cities의 요소들을 for문으로 하나씩 돌면서 확인해보자.

for(let x of cities){
    if(cache.includes(x)) {
        cache = cache.filter(c => c !== x);
        cache.push(x);
        answer += 1;   
    }
    else {
        if(cache.length === cacheSize) cache.shift();
        cache.push(x);
        answer += 5;
    }
}

cache에 요소가 포함된 경우 해당 요소를 cache의 뒤쪽에 추가해준다. 그 후 cache hit의 경우이므로 answer에 +1을 해준다.

cache에 요소가 포함되지 않은 경우, 만약 cache가 cacheSize만큼 꽉 차있다면 cache의 맨 앞 요소를 삭제한다. 이후 cache에 해당 요소를 추가해준다. 이 경우는 cache miss이므로 answer에 +5를 해준다.

이제 return answer를 해주면 끝이다.

전체 코드는 다음과 같다.

전체 코드

function solution(cacheSize, cities) {
    let cache = [], answer = 0;
    
    if(cacheSize === 0) return cities.length * 5;
    
    cities = cities.map(x => x.toLowerCase());
    for(let x of cities){
        if(cache.includes(x)) {
            cache = cache.filter(c => c !== x);
            cache.push(x);
            answer += 1;   
        }
        else {
            if(cache.length === cacheSize) cache.shift();
            cache.push(x);
            answer += 5;
        }
    }
    return answer;
}