[프로그래머스] 캐시 Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17680
LRU 참고: https://velog.io/@haero_kim/LRU-Cache-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

이 문제는 Least Recently Used라는 페이지 교체 알고리즘을 선행지식으로 알고 있어야 문제를 푸는데 도움이 될 것이다. 쉽게 설명하면 가장 오랫동안 사용되지 않은 데이터를 삭제하는 방향으로 로직을 구현하면 된다. 이 말은 즉슨 최근에 사용한 데이터를 최대한 남기면 된다는 말로 풀이될 수 있다.

문제에서 요구하는 것은 LRU 캐싱 방법을 이용해 cities라는 배열에 담긴 모든 도시들을 순회하면 된다. 이때 캐시에 있는 도시는 실행시간이 1 소요되고 캐시에 없는 도시는 실행시간이 5 소요된다. 이렇게 총 순회하는데 걸리는 실행시간을 구하면 된다. 도시 이름에 대소문자 구분이 없기 때문에 upper 또는 lower 케이스로 변환하는 것을 잊지 말자.

아래 코드는 필자가 직접 작성한 코드이다.
LRU가 기억이 안나서 다시 찾아봤는데 cache hit를 할때, 새로 리스트 뒤에 붙여주면 간단하게 구현할 수 있었다.

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