프로그래머스 캐시

2018 카카오 블라인드 채용 문제입니다.

문제풀이

먼저, LRU 알고리즘 : 새로운 페이지가 등장했을 때, 가장 오래전에 사용된 페이지를 캐시에서 삭제합니다.

즉, 캐시 사이즈가 2이고, 캐시에 t=1일 때 A, t=2일 때 B가 들어오면, A와 B는 캐시가 비어있으므로 그냥 캐시에 추가합니다. t=3 일 때 C가 등장한다면, 가장 오래전에 사용된 A를 캐시에서 제거하고 C를 캐시에 추가합니다.

=> 큐 자료구조를 활용합니다.

1. cities에서 city를 꺼내고 대소문자를 구분하지 않는다고 했으므로 전부 대문자로 변환합니다.

2. queue 자료구조로 cache를 선언합니다. cache의 앞에 있을수록 사용한지 오래된 페이지입니다.

위의 예에서 cache는 [A] -> [A, B] -> [B, C]로 변화합니다.

3-1. city가 cache에 있다면 cache에서 city를 삭제하고 city를 다시 넣어줍니다. answer에는 1을 더해줍니다.

* pop()으로 꺼내지 않고 remove(cache)로 지워야합니다. 여기서 city를 지우는 이유는 city를 가장 최근에 사용된 것으로 바꾸기 위해 cache의 맨 끝에 넣기 위함인데, pop()으로 지우면 cache에서 city가 아니라 가장 오래된 것이 지워집니다.

** cache가 [A, B, C] 일 때, B가 들어오면, cache를 [A, C, B]로 바꾸기 위해 B를 지운 후 다시 넣는 것을 말합니다.

3-2. city가 cache에 없다면 cache의 첫번째 요소를 제거(pop())한 후, city를 cache에 넣어줍니다. answer에는 5를 더해줍니다.

*cache의 크기가 cacheSize보다 작을 때는 첫번째 요소를 제거하지 않고 city를 cache에 넣어주는 작업만 수행합니다.

Python Code 

from collections import deque
 
def solution(cacheSize, cities):
    if cacheSize == 0 : return len(cities) * 5
    answer = 5
    cache = deque([cities[0].upper()])
    for city in cities[1:]:
        c = city.upper()
        if c in cache:
            answer +=1
            cache.remove(c)
            cache.append(c)
        else:
            answer += 5
            cache.append(c)
            if len(cache) > cacheSize:
                cache.popleft()
    
    return answer

Line 4 : cacheSize가 0인 경우에는 cities의 요소 수에 5를 곱해 반환합니다.

Line 6 : cache에 cities의 첫번째 요소를 넣은 채 선언합니다. 따라서 answer 역시 5로 초기화합니다.

Line 9 : city가 cache에 있는 경우입니다.

Line 13 : city가 cache에 없는 경우입니다.

 

문제 링크

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