[프로그래머스] 캐시 (Python)

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

코딩테스트 연습 - [1차] 캐시

LRU를 구현하면 된다.

 

나의 풀이

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    answer = 0
    cache = ['']*cacheSize
    for city in cities:
        city = city.upper()
        if city in cache:
            index = cache.index(city)
            cache = cache[:index]+cache[index+1:]+cache[index:index+1]
            answer +=1
        else :
            cache = cache[1:]
            cache.append(city)
            answer +=5
    return answer

 

 

다른 사람 풀이

deque를 활용해서 깔끔하게 구현한 풀이라 가져와 봤다.

곰곰이 생각해보니 LRU를 queue 방식으로 구현하면 직관적으로 이해가 쉽다.

또한 maxlen 파라미터로 최대 큐 크기를 설정할 수 있다.

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time