[프로그래머스] [1차] 캐시

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

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

 

LRU 알고리즘이란 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하는 알고리즘이다.

deque 의 maxlen 을 사용하면 길이 초과시 가장 왼쪽에 있는 데이터(= 가장 최근에 사용된 적이 없는 데이터)가 제거된 후 새 데이터를 담는다.

 

from collections import deque

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

print(solution(3, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'])) # 50