[프로그래머스] level.2 [1차] 캐시

 

 

---

나의 풀이 

function solution(cacheSize, cities) {
    if(!cacheSize) return cities.length * 5
    let time = 0
    cities.reduce((cache, city) => {
        if(cache.includes(city.toLowerCase())){
            cache = cache.filter( x => x !== city.toLowerCase())
            cache.push(city.toLowerCase())
            time += 1
        }else{
            cache.push(city.toLowerCase())
            time += 5
        }
        return cache.length > cacheSize ? cache.slice(1) : cache 
    },[])
    return time
}

 

 

원래는 

 

function solution(cacheSize, cities) {
    if(!cacheSize) return cities.length * 5
    let time = 0
    cities.reduce((cache, city) => {
        if(cache.length > cacheSize) cache.shift()
        if(cache.includes(city.toLowerCase())){
            cache = cache.filter( x => x !== city.toLowerCase())
            cache.push(city.toLowerCase())
            time += 1
        }else{
            cache.push(city.toLowerCase())
            time += 5
        }
        return cache
    },[])
    return time
}

이거였는데  맨 위에처럼 수정하니 속도가 상승하였다.

가급적 shift는 안 쓰려고 한다. 

 

일단 이 문제는 처음에는 어려워보였으나 금방 파악해서 풀었지만 

75점으로 11 15? 18 19가 계속 틀렸다. 

분명 테스트케이스가 다 맞고 몇번을 봐도 코드에 문제가 없는데 하면서 질문하기에서 힌트주시는 분을 봤는데 

LRU를 알아야한다고 하셨다. 

문제에는 LRU를 마치 알고 있다는 듯이 작성되어있는데 필자는 몰라서 공부했다. 

그리고 cache = cache.filter(x=>x !== city.toLowerCase()) 와 push를 추가해줬다. 

즉 hit된 것은 다시 캐쉬배열에서 맨 뒤로 보내서  오랫동안 사용하지 않은 cache가 cacheSize가 가득 찼을때 지워지는 것이다. 

이게 바로 LRU이다. 

 

https://html-jc.tistory.com/445 

[알고리즘] 캐싱 / 페이지교체 알고리즘

 

---