[프로그래머스] [1차] 캐시 파이썬 정답 코드

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

프로그래머스

---

1. 접근 방식

• 새 원소를 추가하면 맨 마지막 원소로 추가되는 cache 리스트를 사용하자.

LRU 알고리즘은 캐시에 존재하는 페이지 중 가장 옛날에 사용된 페이지를 교체하는 페이지 알고리즘이다.

cache 리스트에 append( )로 새로운 페이지를 추가하면, 현재 페이지가 마지막 인덱스로 추가된다. 즉, 최근에 사용한 페이지일수록 cache의 뒤쪽에 위치한다. 이 말은 곧 가장 예전에 사용된 페이지는 0번째 인덱스에 존재한다는 의미이다. 따라서 cache에 존재하지 않는 새로운 페이지가 나타나면, cache의 맨 앞 원소를 삭제하고 새 페이지를 append( ) 해야 한다.

 

• cache의 첫 번째 원소를 삭제하므로, deque 모듈을 사용하자.

일반 리스트에서 pop(0)을 하면, 시간 복자도가 O(n)이다. 반면 pop(0)과 동일한 기능인 deque의 popleft( )는 시간 복잡도가 O(1)이기 때문에 deque를 사용하도록 한다.

 

 

2. 정답 코드

from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    
    answer = 0
    cache = deque()
    for city in cities:
        city = city.lower()
        
        if city in cache:
            cache.remove(city)
            answer += 1
        else:
            if len(cache) == cacheSize:
                cache.popleft()
            answer += 5
            
        cache.append(city)
        
    return answer

 

 

3. 개선 사항

deque 모듈은 maxlen으로 리스트의 길이를 제한할 수 있다. 예를 들어 아래처럼 maxlen=3인 deque를 선언했다고 하자.

data = deque([10, 20, 30], maxlen=3)

이때 새로운 원소인 40을 data에 append( )하면 위 그림과 같은 작업이 발생한다. 40을 추가하고 싶지만 이미 data의 길이가 3이므로, data는 맨 앞에 있는 원소인 10을 제거한 후, 40을 추가한다.

maxlen은 이 문제를 풀 때 매우 유용하다. 위 정답 코드의 반복문에서 cache 리스트의 길이와 cacheSize를 비교하는 조건문이 필요가 없어지기 때문이다. 따라서 maxlen을 사용하여 기존 코드를 개선하면 다음과 같다.

from collections import deque

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