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

문제설명

DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

조건

입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다.

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

처음에 문제를 읽고 무엇을 어떻게 구해야 할지부터 난관이었다. ㅠㅠ

일단 조건에 있는 키워드 부터 무엇인지 알아보았다.

LRU(Least Recently Used)

페이지 교체 알고리즘 중 하나로, 페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법이다.

캐시 히트(Cache hit)

CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우

캐시 미스(Cache miss)

CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우

이 정보들로 의사코드를 작성해보았다.

실패한 의사코드

function solution(cacheSize, cities) {
    let count = 0;
    let arr = [];
    for(cities 개수){
      arr[i]소문자로 통일;
      arr에 cities[i] 추가;
      if(arr.length === cacheSize){  //캐시 사이즈에 걸리는 경우
        if(arr에 cites[i]가 있다){
          해당 도시를 지우기;
          count +=1;
        } else if(arr에 cites[i]가 없다){
          count += 5;
          arr[0]지우기(가장 오래된 항목)
        }
      } else count += 5; //캐시 사이즈에 걸리지 않는 경우
    }
    return count;
 }

통과하지 못했다....

실패 원인

1) arr에 cities[i] 추가하는 타이밍
arr에 cites[i]가 있는지를 filter 메서드를 통해 구현했었는데 그러다보니 cities[i]도 arr에 포함되어 있는 상태로 나와 for문이 돌아갈 때마다 count +=1으로 실행되었다.
=> cites[i]가 arr에 포함된 상태가 아니어야 함.

2) 캐시 사이즈에 걸리지 않는 경우에도 캐싱하는 값이 arr에 포함되어 있을 수 있다는 것을 간과했다.

3) 캐시 크기가 0인 경우를 고려하지 않았다.

이 세가지를 바탕으로 하여 코드의 위치와 문법 등을 재작성했다.

재작성한 의사코드

function solution(cacheSize, cities) {
    let count = 0;
    let arr = [];
    if(캐시크기가 0인 경우)return cities.length*5;
    
    for(let i = 0; i <cities.length; i++){
        arr[i]소문자로 통일;
        let cacheHit = arr.filter(cities[i]와 다른 값); //cities[i]와 다른 값만 추출된 상태
        if(추출된 배열과 arr가 다르다){ //일치하는 도시가 있는 경우
            count += 1; 
            cacheHit를 arr로 변경; 
        }else count +=5; // 일치하는 도시가 없는 경우
       
        if(cache miss이면서, 캐시크기에 걸리는 상황){ 
            오래된 항목을 제거한다;
        }
        arr에 cities[i] 추가;
    }
    return count;
}

최종적으로 작성한 코드는 이렇다.

최종 코드

function solution(cacheSize, cities) {
    let count = 0;
    let arr = [];
    if(cacheSize === 0)return cities.length*5;

    for(let i = 0; i <cities.length; i++){
        cities[i] = cities[i].toLowerCase();
        let cacheHit = arr.filter(e => e !== cities[i]); //같은 이름의 도시가 있는지 검색
        if(cacheHit.length !== arr.length){ //있다면
            count += 1; //cache hit
            arr = cacheHit; //도시 캐싱 시 최근 참조된 상태로 변경
        }else count +=5; // 없다면 cache miss

        if(arr.length === cacheSize){ //cache miss이면서, 캐시크기에 걸리는 상황
            arr.shift(); //오래된 항목을 제거한다.
        }
        arr.push(cities[i]);
    }
    return count;
}