[Algorithm/JavaScript] 캐시

Programmers Level.2 Question Review ✍🏻

문제출처: https://programmers.co.kr/learn/courses/30/lessons/17680#

문제

문제 보러가기

제출답안

오답 ❌

function solution(cacheSize, cities) {
    //cacheSize만큼 처음 들어오는 도시의 수를 저장한다. 큐 형식으로 가장 오래된 요소가 빠지고 최근에 쓰인 요소가 뒤로 추가된다.
    const cache = [];
    let operationTime = 0; 
    let index; //i + 1부터는 요소가 있는지 검사. 
    //cacheSize만큼 도시 저장.   
    for (let i = 0; i < cacheSize; i++){
        cache.push(cities[i]);
        operationTime += 5;
        index = i;
    }
    
    for (let j = index + 1; j < cities.length; j++){
        let hasEl = false;
        for (let k = 0; k < cache.length; k++){
            if (cities[j].toUpperCase() === cache[k].toUpperCase()){
                //cache배열에 도시명이 이미 있는 경우 
                hasEl = true;
                operationTime++; 
                const removedEl = cache.splice(k, 1);
                cache.push(removedEl[0]); //cache[k]
                break;
            }
        }
        //cache배열에 도시명이 없는 경우
        if (!hasEl){
            operationTime += 5;
            cache.shift();
            cache.push(cities[j]);
        }
    }        
    if (!cacheSize) operationTime = cities.length * 5;
    return operationTime;
}

최종제출답안 ⭕️

function solution(cacheSize, cities) {
    //cacheSize만큼 처음 들어오는 도시의 수를 저장한다. 큐 자료구조로 가장 오래된 요소가 빠지고 최근에 쓰인 요소가 뒤로 추가된다.
    const cache = new Array(cacheSize).fill("0");
    let operationTime = 0; 
    let index; //i + 1부터는 요소가 있는지 검사. 
    
    for (let j = 0; j < cities.length; j++){
        let hasEl = false;
        for (let k = 0; k < cache.length; k++){
            if (cities[j].toUpperCase() === cache[k].toUpperCase()){
                //cache배열에 도시명이 이미 있는 경우 
                hasEl = true;
                operationTime++; 
                const removedEl = cache.splice(k, 1);
                cache.push(removedEl[0]);
                break;
            }
        }
        //cache배열에 도시명이 없는 경우
        if (!hasEl){
            operationTime += 5;
            cache.shift();
            cache.push(cities[j]);
        }
    }        
    if (!cacheSize) operationTime = cities.length * 5;
    return operationTime;
}

오늘의 Lesson

• cache hit이나 cache miss 와 같이 생소한 개념들을 포함한 문제라 문제를 이해하는 데에도 시간이 걸렸다.
  새로 알게 된 개념들 :

  • cache hit: 참조하려는 데이터가 캐시에 존재하는 경우 해당 캐시를 조회하는 것.
  • cache miss: 참조하려는 데이터가 캐시에 존재 하지 않는 경우.
  • LRU(Least Recently Used): 캐시에서 메모리를 다루기 위해 사용되는 알고리즘으로, 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.
    출처: https://jins-dev.tistory.com/entry/LRU-Cache-Algorithm-정리 [Jins' Dev Inside]

• 처음 접근했던 방법은 cacheSize를 길이로 갖는 cache 배열을 만들어 cities의 요소들을 앞에서부터 순차적으로 미리 채워놓는 것이었다. 미리 채워진 요소 수 * 5를 해서 실행시간의 default값을 설정하려는 것이었다.
  코드 실행용으로 주어진 테스트 케이스들은 모두 통과했지만, 정작 제출시에는 보이지 않는 3~4가지 테스트 케이스를 계속 통과하지 못해서 길을 잃은 상태였다.
• 팀원들의 도움을 받아 실패한 것으로 예상되는 테스트 케이스를 추가로 만들어 실행해 본 결과, cacheSize > cities.length인 아래 두 가지 경우에는 적용이 되지않았다. (팀원들이 아니었다면 스스로 이런 테스트 케이스를 생각해낼 수 있었을 지 아직도 의문스럽다)
  1) solution(3, ["a", "a"])
  2) solution(3, ["a", "b"])
• 풀고나니 이렇게까지 끌 문제가 아니었다는 생각이 들지만 무려 반나절을 쏟아부었다...🤯
  케이스를 다양하게 생각하지 못해서 한정적으로 적용되는 접근방법만을 생각했기 때문이다. 그래서 허점을 발견하고나서 대대적인 수정이 필요했다(거의 설계단계부터).
  알고리즘을 풀면서 테스트 케이스를 추가했던 경우가 손에 꼽는데 앞으로는 테스트 케이스 추가하기 기능을 적극 활용해야겠다는 생각이 들었다. 다양한 케이스를 예측해보면서 보여지는 것 이상으로 확장성이 넓은 코드를 구상할 수 있는 노력이 필요하다.