운영체제의 메모리 단원에서 배우는 LRU기법을 이용하여 캐시 히트/미스 여부에 따라 전체 실행시간을 계산하는 문제다.
LRU 알고리즘은 가장 안쓴 메모리를 캐시에서 삭제하는 간단한 방법이다.

캐시사이즈가 최대 30이므로 queue를 이용하지 않고 단순 리스트로 구현하였다. 그런데 7번, 17번에서 틀렸었다.

0 <= cacheSize <= 30, 즉 캐시사이즈가 0일수 있다

그래서 이 경우에만 예외처리를 하고 통과하였다.
get_index()라는 함수를 정의하였는데, 이는 리스트의 index()메소드는 리스트에 없는 원소를 찾으려 하면 ValueError가 나기 때문이다. (파이썬은 음수 인덱스도 지원하므로 에러로 처리한 것으로 생각된다...)

나의 코드

def get_index(L, item):
    for i, x in enumerate(L):
        if x == item:
            return i
    return -1

def solution(cacheSize, cities):
    answer = 0
    if cacheSize == 0:
        return 5 * len(cities)
    memory = []
    for city in cities:
        city = city.lower()
        idx = get_index(memory, city)
        
        # miss
        if idx == -1:
            if len(memory) == cacheSize:
                memory = memory[1:]
            memory.append(city)
            answer += 5
        # hit
        else:
            del memory[idx]
            memory.append(city)
            answer += 1    
                
    return answer

다른 사람 풀이

deque(maxlen=cacheSize)를 이용하여 일관성있는 코드를 작성했다😮