[JS] [1차] 캐시

 

 

난이도: Lv.2

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

프로그래머스

 

 

알고리즘

1. 참고로 문제에서 도시 이름은 대소문자를 구분하지 않는다고 했기 때문에 모든 도시 이름을 소문자 또는 대문자로 바꿔준 후 진행한다.

2. 캐시에 들어가 있는 도시 이름을 나타내는 cacheMemory 배열과 도시 이름이 언제 캐시에 들어갔는지 나타내는 cacheStatus 배열을 선언한다.

3. miss에는 두 종류가 있다. 캐시가 꽉 차지 않아서 발생하는 경우와 캐시가 꽉 차서 캐시 안에 있는 것들 중 하나를 바꿔야 하는 경우가 있다.

전자의 경우 cacheMemory 배열과 cacheStatus 배열에 도시 이름과 도시 인덱스를 각각 push()한다. 

후자의 경우 cacheStatus 배열을 순회하며 가장 오래 전에 참조된 인덱스를 찾는다. 찾은 인덱스에 위치한 cacheMemory의 원소와 cacheStatus의 원소를 각각 교체할 도시 이름과 도시 인덱스로 바꾼다.

4. cacheMemory 배열에 도시 이름이 캐싱되어 있으면 hit다. 이 경우 cacheStatus 배열의 해당 인덱스를 업데이트한다.

 

 

 

코드

function solution(cacheSize, cities) {
    var answer = 0;
    const cacheMemory = [];
    const cacheStatus = [];

    // 모든 도시 이름을 소문자로 변경
    cities = cities.map((city) => city.toLowerCase());

    for (let city = 0; city < cities.length; city++) {
        const foundIdx = cacheMemory.findIndex((e) => e === cities[city]);
        if (cacheMemory.length < cacheSize && foundIdx === -1) { // 캐시 덜 채워져서 생기는 miss
            cacheMemory.push(cities[city]);
            cacheStatus.push(city);
            answer += 5;
        } else if (foundIdx !== -1) { // hit
            cacheStatus[foundIdx] = city;
            answer += 1;
        } else { // miss -> 캐시 교체
            let minIdx; // 가장 오래전에 참조된 인덱스
            let min = cities.length;
            for (let i = 0; i < cacheSize; i++) {
                if (min > cacheStatus[i]) {
                    min = cacheStatus[i];
                    minIdx = i;
                }
            }
            cacheMemory[minIdx] = cities[city];
            cacheStatus[minIdx] = city;
            answer += 5;
        }
    }

    return answer;
}

 

 

주저리

운영체제 시간에 지겹도록 했던 페이지 교체 알고리즘 중 하나라서 이해하는데 시간도 별로 안 들이고 금방 풀었다. 가장 오래전에 참조된 인덱스 찾아낼 때 Math.min 함수랑 findIndex 함수 써서 찾으면 보기도 좋고 간단하긴 한데 배열 순회를 두 번 해야 된다는 단점이 있다. 그래서 그냥 min이랑 minIndex 찾도록 내가 구현하긴 했는데 이렇게 하면 메모리 쓰기가 더 많은가 싶어서 생각을 해봤는데 메모리 쓰기는 더 많을 수 있어도 속도는 내가 구현하는 게 더 빠른 것 같다는 결론에 도달했지만 실제로 돌려보면 비슷하다. 전자는 내장 함수 사용, 후자는 내가 구현한 결과