[Programmers / Level2] 캐시

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

프로그래머스

---

 

<내 코드 - list>

def solution(cacheSize, cities):
    if cacheSize == 0: return len(cities) * 5
    cache = []
    time = 0
    
    for city in cities:
        city = city.lower()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            time += 1
        else:
            time += 5
            if len(cache) >= cacheSize and cache:
                cache.pop(0)
            cache.append(city)

    return time

 

-> 캐싱에서의 LRU알고리즘에 대한 지식이 필요한 문제였다. Least Recently Used의 줄임말로 왼->오 로 갈수록 최신의 데이터로 판단하여 구현한다.

만약 캐시안에 데이터가 존재한다면 최신의 데이터로 간주해야 하므로, 리스트에서 빼고 다시 넣어주는 과정을 해준다.

여기서는 list로 구현했지만 dq자료형으로 하면 시간복잡도를 줄일 수 있을것같아서 변경해봤다.

 

<내 코드 - deque>

def solution(cacheSize, cities):
    if cacheSize == 0: return len(cities) * 5
    cache = []
    time = 0
    
    for city in cities:
        city = city.lower()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            time += 1
        else:
            time += 5
            if len(cache) >= cacheSize and cache:
                cache.pop(0)
            cache.append(city)

    return time

 

 

예상대로 미약하게나마 실행시간이 줄은것을 볼 수 있다.

 

그리고 하나더 deque를 사용할 때 팁이라면 팁인 maxlen이 있다.

cache = collections.deque(maxlen=cacheSize)

-> deque를 사용할 때 maxlen이라는 인자를 통해 최대캐시크기를 조정할 수 있다.