[Javascript/PGS] Lv.2 : [1차] 캐시 (2018 KAKAO)

 

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

---

프로그래머스 레벨 2.

캐시 저장공간을 구현하는 단순 구현 문제이다.

 

캐시 교체 알고리즘은 LRU(Least Recently Used)이므로, 최근 사용했던 순위를 기억해주어야 한다.

따라서, 캐시 배열에 가장 최근 사용한 것은 1로,

나머지 것들은 해당 위치의 값에 1씩 더해주었다.

 

주의할 점은 대소문자 구분을 없애야 한다는 것! 나의 경우는 js라서 toLowerCase 함수를 사용했다.

 

 

나의 풀이

function solution(cacheSize, cities) {
    var answer = 0;
    let cache = new Array(cacheSize).fill(["",0]);
    
    cities.forEach(city=>{
        city = city.toLowerCase();
        let idx = -1;
        // 캐시에서 찾기
        for(let i=0; i<cacheSize; ++i){
            if(cache[i][0] == city){
                idx = i;
                break;
            }
        }
        // 캐시 hit
        if(idx>=0) {
            answer += 1;
            for(let i=0; i<cacheSize; ++i){
                if(i==idx) cache[idx] = [city, 1]; // 가장 최근 사용 = 1
                else cache[i][1] += 1;
            }
        }
        // 캐시 miss
        else {
            answer += 5;
            let deleteIdx = 0;
            let maxValue = 0;
            for(let i=0; i<cacheSize; ++i){
                if(cache[i][1]==0){
                    deleteIdx = i;
                    break;
                }
                if(maxValue < cache[i][1]){
                    maxValue = cache[i][1];
                    deleteIdx = i;
                }
            }
            cache[deleteIdx] = [city,1];
            for(let i=0; i<cacheSize; ++i){
                if(i==deleteIdx || cache[i][1]==0) continue;
                cache[i][1] += 1;
            }
        }
    })
    
    return answer;
}