[JS] 캐시

오랜만에 LRU캐시에 대해 학습하였다.

 

 

LRU 캐시란

 

Least Recently Used

 

 

즉, 가장 오래전에 사용된 데이터를 제거하는 방식을 가진 캐시이다.

 

 

처음에 이왕 추상화를 해볼꺼 더블 링크드 리스트를 구현해서 만드려고 했는데 어차피 캐시의 크기가 최대 30개이고 귀찮음이 발동해서 LRU 클래스를 만들어 보는것으로 타협해보았다.

 

LRU클래스는 캐시와 maxSize만 가지고 있다.

 

set명령어로 캐시에 값을 넣을때 캐시에 값이 있다면 해당 값을 캐시의 맨 앞으로 보내주고, 실행시간인 1을 반환해준다.

 

캐시에 아무것도 없다면 캐시의 맨앞에 새로운값을 넣어주고 만약 캐시의 크기가 초과되었다면 가장 오래된 값을 캐시에서 제거해준다. 그리고 실행시간인 5를 반환해준다.

 

 

문제에서 대소문자를 구별한다고 하지 않았으므로 들어오는 값들을 모두 소문자로 바꿔준 이후, set명령어로 실행시간들을 더해주었다.

 

 

 

class LRU {
    constructor (cacheSize){
        this.cache = []
        this.maxSize = cacheSize
    }
    
    set(val) {
        const idx = this.cache.indexOf(val)
        if (idx!==-1) {
            this.cache = [this.cache[idx],...this.cache.slice(0,idx),...this.cache.slice(idx+1)]
            return 1
        }
        
        this.cache.unshift(val)
        if (this.maxSize < this.cache.length)  this.cache.pop()
        return 5
    }
}

function solution(cacheSize, cities) {
    cities = cities.map(v => v.toLowerCase())
    const cache = new LRU(cacheSize)
    let ret = 0
    for (const city of cities) {
        ret += cache.set(city)
    }
    return ret
    
    
}