[Python] 프로그래머스 - [1차] 캐시(LRU/Deque)

◈ 오류 정정 및 피드백 환영

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

---

🔎문제 분석

큐(queue)의 구조인 FIFO(First In Firsts Out)는 새로운 데이터를 저장할 때 공간이 부족할 경우 가장 오래된 데이터를 제거한다. 이와 달리 LRU(Least Recently Used)는 가장 오랫동안 사용하지 않았던 데이터를 제거한다.

즉, 저장된 시간이 가장 길었던 데이터일지라도 최근에 참조된 이력이 있다면 제거하지 않는다.

1, 2, 1, 3을 크기가 3인 캐시에 저장한 상태([1 2 3])에서 새로운 데이터인 4를 어떻게 저장해야 할지 비교해 보자.

• FIFO - 가장 오래된 데이터인 1을 제거 → [2 3 4]
• LRU - 1이 최근에 참조되었다는 점을 고려해 2번째로 오래된 2를 제거 → [1 3 4]

특정 위치의 원소를 제거해야 하므로 덱(deque)으로 접근하면 된다.

 

데이터마다 참조 횟수를 저장하는 것은 불필요한 메모리를 사용하는 셈이기 때문에 참조되었을 경우 해당 데이터를 맨 오른쪽으로 옮겨 우선순위를 나타내면 된다.

if I in cache:
    cache.remove(I)
    cache.append(I)

위 예시의 경우 3번째 순서에서 1이 참조되었을 때 캐시를 [1 2] 에서 [2 1]로 변경해야 한다.

이렇게 순서를 변경하면 공간이 부족할 때마다 참조 횟수를 파악할 필요 없다. 항상 맨 왼쪽에 있는 데이터를 제거해도 되기 때문이다.

🤦‍♀️유의 사항

 else:
    cache.append(I)
    if len(cache) > cacheSize:
        cache.popleft()

append를 먼저 하지 않으면 비어있는 덱에서 원소를 뽑아야 하는 상황이 생길 수 있다.

---

 

 

from collections import deque

def solution(cacheSize, cities):
    cache = deque([])
    answer = 0
    for i in cities:
        I = i.upper()
        if I in cache:
            cache.remove(I)
            cache.append(I)
            answer += 1
        else:
            cache.append(I)
            if len(cache) > cacheSize:
                cache.popleft()
            answer += 5
    return answer

---

👀다른 풀이

dequedml maxlen 옵션을 사용해서 공간이 부족할 경우 캐시에 저장하지 않는 과정을 생략할 수 있다.

---

from collections import deque

def solution(cacheSize, cities):
    cache = deque(maxlen=cacheSize)
    answer = 0
    for i in cities:
        I = i.upper()
        if I in cache:
            cache.remove(I)
            cache.append(I)
            answer += 1
        else:
            cache.append(I)
            answer += 5
    return answer