[JS][프로그래머스]1차_캐시

문제 번호

프로그래머스

 

 

알고리즘 분류

 

 

문제 풀이

 LRU가 무엇인지 알아야하는 문제다. 정확하게 알 필요는 없고 가장 오랫동안 사용되지 않은 페이지를 교체한다라는 것만 알면 된다.

 그리고 검색한 도시가 캐시되어 있다면 해당 도시가 최근에 검색 되었다고 업데이트 해야한다.

예를들어 [A,B,C] 라는 순서대로 검색을 진행 했었으면, A가 가장 오랫동안 사용되지 않은 페이지에 해당된다. 이때 다음 번에 A를 검색했으면 [B,C,A]로 상태를 업데이트 해주어야 한다. 

 cache된 데이터를 담아주는 자료구조로 배열을 선택했기 때문에 업데이트를 해주는 방법으로 splice후 push 하는 방법을 선택했다.

            cache.splice(No,1);
            cache.push(city);

 주어진 모든 도시들을 탐색하면서 각각의 도시들이 cache 되어 있는지 확인하면서 소요시간을 계산해주면 된다.

 

 단 이때 cacheSize가 0인 경우를 조심해야한다. cacheSize가 0인 경우 매번 cache miss가 나면서 5초가 소요되므로 해당 부분의 예외처리를 잘 해주어야 한다.

    if(cacheSize === 0)
        return cities.length*5;

 

전체코드

/*
    가장 오랫동안 사용되지 않은 페이지를 교체함.
    1. 캐시 사이즈 크기의 배열을 만듬. (30)
    2. 도시의 이름이 배열에 있는지 확인(10^5)
        3*10^6
    3. LRU update
*/

function solution(cacheSize, cities) {
    let answer = 0;
    
    const cache = [];
    
    if(cacheSize === 0)
        return cities.length*5;
    
    cities.forEach(city => {
        city = city.toUpperCase()
        
        const No = cache.indexOf(city)        
        
        if(No !== -1) {
            answer += 1;
            
            cache.splice(No,1);
            cache.push(city);
        } else {
            answer += 5;
            
            if(cache.length < cacheSize) {
                cache.push(city);
            } else {
                cache.shift();
                cache.push(city);   
            }            
        }
    })
    return answer;
}

 

특이사항

공식 해설

카카오 신입 공채 1차 코딩 테스트 문제 해설