[프로그래머스] 캐시(LRU) / Python / 2018 KAKAO BLIND RECRUITMENT

https://programmers.co.kr/learn/courses/30/lessons/17680?language=python3

프로그래머스

---

---

Solution

문제 유형 : 캐시 교체 알고리즘 (LRU)

 

도시 이름이 대소문자 구분을 하지 않으므로 소문자(lower)나 대문자(upper)로 통일 시킨다.

LRU 알고리즘을 쓰는데, 입력으로 주어지는 cacheSize가 0일 때의 예외처리를 해준다.

cacheSize가 0이면, 캐시가 없으므로 모든 도시들에 대해 cache miss가 된다. 따라서 cities의 길이 * 5를 리턴.

 

• 도시가 캐시 안에 없을 경우 (cache miss)

1. 캐시 크기와 cacheSize를 비교하고 캐시 크기가 작을 경우 그냥 현재 도시를 캐시 안에 넣어준 후 실행시간에 5를 더해준다. 
2. 캐시 크기가 클 경우 캐시에서 가장 오래된 값(인덱스 : 0)을 제거하고 현재 도시를 넣어준다. 그리고 실행시간에 5를 더해준다.

• 도시가 캐시 안에 있을 경우 (cache hit)

1. 해당 도시를 캐시에서 제거하고, 다시 마지막 인덱스로 넣어준 후 실행시간에 1을 더한다.