[Python] 프로그래머스 Lv2. 캐시

문제

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

프로그래머스

문제 요약

도시가 들어오고 캐시 크기가 정해져 있을때, LRU 방식으로 내보내고 들어오고를 반복한다고 하면 얼마나 걸리는지 측정하면 되는 문제였다.

LRU를 안다면, 쉽게 풀 수 있는 문제!

---

풀이

LRU는 가장 오래 전에 사용한 것을 자리가 부족할때 먼저 빼내는 방식이다.

때문에 새로 들어오는 값들이 이미 캐시 안에 있다면 remove한 다음에 새로 뒤에 넣어주는 방식으로
제일 앞에 있는게 가장 오래 전에 사용했고 끝에 있는 게 최근에 사용한 것이다.

있을때는 +1, 없을때는 +5. 캐시 크기에 넘어가면 내보내고 새로운 걸 뒤에 넣어주는 방식으로 진행하면 된다.

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) *5

    cache = []         
    time = 0

    for city in cities:
        c = city.lower()
        if c in cache:       
            cache.remove(c)
            cache.append(c)
            time += 1
        else:                 
            if len(cache) == cacheSize:
                cache.pop(0) 
            cache.append(c)
            time += 5
    return time

시간복잡도

도시 배열을 한 바퀴 돌면서 캐시 사이즈 따라 remove랑 pop(0)을 진행하기 때문에
O(n*k)이다.