[1차] 캐시 (level2)

링크

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

문제

캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다. 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력하라.

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용하며 cache hit일 경우 실행시간은 1이다. cache miss일 경우 실행시간은 5이다.

예제로 이해

cacheSize와 cities가 다음과 같이 주어질 때 각 도시가 처리되는 과정은 아래와 같다.

cacheSize = 5
cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]

1. Jeju, [] => ["Jeju"], 실행시간 = 5
2. Pangyo, ["Jeju"] => ["Pangyo", "Jeju"], 실행시간 = 10
3. Seoul, ["Pangyo", "Jeju"] => ["Seoul", "Pangyo", "Jeju"], 실행시간 = 15
4. NewYork, ["Seoul", "Pangyo", "Jeju"] => ["NewYork", "Seoul", "Pangyo", "Jeju"], 실행시간 = 20
5. LA, ["NewYork", "Seoul", "Pangyo", "Jeju"] => ["LA", "NewYork", "Seoul", "Pangyo", "Jeju"], 실행시간 = 25
6. SanFrancisco, ["LA", "NewYork", "Seoul", "Pangyo", "Jeju"] => ["SanFrancisco", "LA", "NewYork", "Seoul", "Pangyo"], 실행시간 = 30
7. Seoul, ["SanFrancisco", "LA", "NewYork", "Seoul", "Pangyo"] => ["Seoul", "SanFrancisco", "LA", "NewYork", "Pangyo"], 실행시간 = 31
8. Rome, ["Seoul", "SanFrancisco", "LA", "NewYork", "Pangyo"] => ["Rome", "Seoul", "SanFrancisco", "LA", "NewYork"], 실행시간 = 36
9. Paris, ["Rome", "Seoul", "SanFrancisco", "LA", "NewYork"] => ["Paris", "Rome", "Seoul", "SanFrancisco", "LA"], 실행시간 = 41
10. Jeju, ["Paris", "Rome", "Seoul", "SanFrancisco", "LA"] => ["Jeju", "Paris", "Rome", "Seoul", "SanFrancisco"], 실행시간 = 46
11. NewYork, ["Jeju", "Paris", "Rome", "Seoul", "SanFrancisco"] => ["NewYork", "Jeju", "Paris", "Rome", "Seoul"], 실행시간 = 51
12. Rome, ["NewYork", "Jeju", "Paris", "Rome", "Seoul"] => ["Rome", "NewYork", "Jeju", "Paris", "Seoul"], 실행시간 = 52

코드

function solution(cacheSize, cities) {
    if(cacheSize === 0) return cities.length * 5
    
    let result = 0
    let cache = new Array(cacheSize).fill("")
    let lower = ""
    
    cities.map(el => {
        lower = el.toLowerCase()
        if(cache.includes(lower)) {
            cache.splice(cache.indexOf(lower), 1)
            cache = [lower, ...cache]
            result += 1
        } else {
            cache.pop()
            cache.unshift(lower)
            result += 5
        }
    })
    
    return result
}

코드 풀이

가장 먼저 캐시의 사이즈가 0이면 LRU(Least Recently Used)를 적용할 것도 없이 도시 하나를 찾는데 무조건 cache miss가 발생하기 때문에 배열의 길이 x 5를 반환한다.

cities로 map을 돌리는데 대소문자를 구분하지 않기 때문에 각 요소를 소문자로 먼저 변환을 실시한다. 변환된 글자를 캐시 배열에 포함되는지 확인을 한다.

포함이 된다면 cache hit가 발생하므로 실행 시간에 +1을 진행하고, 캐시에서 해당 글자를 가장 앞으로 옮기는 과정을 실시한다. 캐시 배열에서 해당 글자를 splice로 제거하고 스프레드 연산자를 활용하여 가장 앞에 현재 도시가 오도록 캐시를 새로 만든다.

반대로 포함되지 않는다면 cache miss가 발생하므로 실행 시간에 +5를 진행한다. 캐시에 해당 글자가 없기 때문에 캐시에서 가장 오래된 도시 이름을 삭제하고 가장 앞에 현재 비교 중인 도시를 넣어 캐시에 넣어준다.