프로그래머스 - Level 2. [1차] 캐시 / JavaScript (js)

문제설명

문제분석

이 문제의 조건에 나타나있듯이 캐시 교체 알고리즘은 LRU(Least Recently Used) 알고리즘을 사용합니다. LRU 알고리즘은 캐시를 확인하면서, 오랫동안 사용되지 않은 페이지(이 문제에서는 도시 이름)를 삭제하고, 최근에 사용된 페이지를 추가하는 알고리즘입니다. 삭제와 추가를 효율적으로 진행해야하기때문에, 객체를 사용하여 구현하는 것이 가장 효율적입니다.

• 도시이름 배열을 순회하면서, 객체에 존재하면 5를 추가, 존재하지 않으면 1을 추가합니다.
• 객체에 존재하는 도시이름의 수가 캐시 사이즈보다 크면, 가장 오래된 키-값 페어를 제거합니다.

문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다.

이해하기 쉽게 코드작성하기

function solution(cacheSize, cities) {
    let answer = 0;
    
    cities.reduce((a, c) => {
        c = c.toLowerCase();
        if(a[c] === undefined) {
            answer += 5;
        } else {
            answer += 1;
            delete a[c];
        }
        a[c] = true;
        if(Object.keys(a).length > cacheSize) {
            delete a[Object.keys(a)[0]];
        }
        return a;
    }, {});
    
    return answer;
}

사실 알고리즘을 적용하면 되는 문제라서 딱히 설명할 게 없습니다. 이래서 알고리즘 공부가 중요합니다... 앞으로 시간이 좀 난다면 알고리즘에 대한 설명도 정리해봐야겠습니다.