Level 2️⃣ - 캐시 (2018 KAKAO BLIND RECRUITMENT)

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

프로그래머스

 

어려운 문제는 아니지만 컴퓨터 구조를 활용한 알고리즘 문제라는 재밌는 유형이기에 정리한다.

 

캐쉬 교체 알고리즘을 활용해서 코드를 구현해야한다.

LRU (Least Recently Used) 에 대해 자세한 설명이 나와있지 않기 때문에 해당 개념을 모른다면 문제를 풀 수 없다.

LRU는 가장 오랫동안 참조하지 않은 데이터를 교체하는 알고리즘이다.

 

캐시 큐에 데이터가 있다면 cache hit이다.

이 경우에는 해당 데이터를 찾아서 캐시 큐의 맨 뒤로 보내주면 된다.

캐시 큐에는 맨 앞에서부터 오랫동안 참조되지 않은 순서대로 배치할 것이다.

 

만약 캐시 큐에 데이터가 없다면 cache miss이다.

이 경우에는 캐시 큐에 자리가 있는 경우, 캐시 큐에 자리가 없는 경우를 고려해야한다.

캐시 큐에 자리가 없는 경우라면 가장 오랫동안 사용하지 않은 데이터를 교체하면 된다. 그 데이터는 캐시 큐의 맨 마지막에 위치한다.

#1 캐시에 데이터가 있는 경우 
if(cache.includes(city)) ➡ cache hit
idx = cache.indexOf(city)
item = cache.splice(idx, 1)
cache.push(item[0])

#2 캐시에 데이터가 없는 경우 ➡ cache miss
#2-1 캐시에 자리가 꽉 찬 경우
if(cache.length === cacheSize)
cache.shift()
cache.push(city)
#2-2 캐시에 자리가 있는 경우
cache.push(city)

코드

단, 구현 시 주의할 점이 있다.

캐시 사이즈가 0인 경우에는 캐시에 어떤 값도 넣을 수 없다. 이 경우에는 cache miss로 간주해서 총 실행시간에 5만 더해주고 캐시에는 아무값도 들어가지 않도록 구현해야한다.

항상 반례를 생각할 때 구간의 최소조건과 최대조건을 고려하자. 

function solution(cacheSize, cities) {
    let ret = 0;
    const cache = [];
    for(let city of cities){
        if(cacheSize === 0){
            ret += 5;
            continue;
        }
        city = city.toUpperCase();
        if(cache.includes(city)){
            ret += 1;
            const idx = cache.indexOf(city);
            const item = cache.splice(idx, 1);
            cache.push(item[0]);
        }
        else {
            ret += 5;
            if(cache.length === cacheSize) {
                cache.shift();
                cache.push(city);
            }
            else {
                cache.push(city);
            }
        }
    }
    
    return ret;
}