[Python] deque를 이용한 LRU 구현

문제 출처: 2017 카카오 신입 공채 블라인드 코테 3번 캐시

LRU (Least Recently Used): 캐시 교체 전략 중 하나로, 가장 오래전에 사용된 아이템을 버리는 방식.
파이썬에서는 deque의 maxlen 파라미터를 사용하여 LRU를 구현할 수 있다 😀

cache = collections.deque(maxlen=cacheSize)

데크의 최대 크기(maxlen)를 초과할 경우 가장 오래된 항목부터 제거된다.

문제 풀이

def solution(cacheSize: int, cities: List[str]) -> int:
	elapesd: Int = 0
    cache = collections.deque(maxlen=cacheSize)
    
    for c in cities:
    	c = c.lower()
        # cache hit 시 재삽입 처리
        if c in cache:
        	cache.remove(c)
            cache.append(c)
            elapsed += 1
        else:	# cache miss 시 삽입만
        	cache.append(c)
            elapsed += 5
            
	return elapsed