[N시간만에 끝내는 Python 코딩테스트] 4편 2018 카카오 코딩테스트 3번 캐시 (LRU)

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

프로그래머스

 

https://www.youtube.com/watch?v=XoQUiPHhAFw&list=PLkfUwwo13dlUW9tPNXYnr-6EmYuUOvlko&index=4

 

 

LRU 알고리즘 (Least Recently Used Algorithm) 

가장 오랫동안 참조되지 않은 페이지를 교체하는 기법 

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)

 

from collections import deque

def solution(cacheSize, cities):
    I = [''] * cacheSize
    cache = deque(I, maxlen=cacheSize)  # 큐의 사이즈를 정할 수 있다. 
    answer = 0 
    for city in cities:
        city = city.lower()         # 문자 소문자로 통일이 필요함 
        if city in cache:           # cache hit일 경우 
            cache.remove(city)      # cache에 있는 도시를 제거하고 
            cache.append(city)      # 가장 최신 위치 즉 가장 뒤에 넣는다 
            answer += 1
        else:                       # cache miss일 경우 
            cache.append(city)      # cacheSize를 넘으면 자연스럽게 가장 오래된 도시는 사라지고 새 도시가 들어옴 
            answer += 5
    return answer

if __name__ == '__main__':
    cacheSize = 3
    cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
    
    print(solution(cacheSize, cities))

 

deque에 큐 사이즈를 정할 수 있는것을 이제 알았다. 

maxlen을 통해 큐 사이즈를 정할 수 있다