프로그래머스 2단계 - [1차] 캐시

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

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

 

LRU 알고리즘 참고:

https://gingerkang.tistory.com/26

[Python] LRU(Least Recently Used) 알고리즘

 

LRU 알고리즘에 대해 검색해보고 알고리즘을 익힌 다음에 직접 구현해보았다.

한마디로 정의하면 가장 오래된 페이지를 버리고 새롭게 추가하는 알고리즘이다.

가장 오래된 페이지는 앞으로도 계속 사용할 일이 없다는 이론을 토대로 만들어진 알고리즘이다.

 

다만 원래 코드에서는 cacheSize가 0일 때가 고려되지 않았는데, cacheSize가 0인 경우 pop이 되지 않고 append도 되지 않도록 if문 하나를 넣어서 처리해주었다.

 

---

Python

"""
Created by MinSeo on 2022/02/13.
Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
 
"""
def solution(cacheSize, cities):
    answer = 0
    cache = []
    for city in cities:
        temp = city.lower()
        if temp not in cache:
            if len(cache) >= cacheSize and cacheSize != 0:
                cache.pop(0)
            if cacheSize != 0:
                cache.append(temp)
            answer += 5
        else:
            answer += 1
            cache.pop(cache.index(temp))
            cache.append(temp)
    return answer