문제
접근
캐시 배열을 하나만들어두고, 정말 LRU 알고리즘을 하듯이 구현해야한다.
LRU 알고리즘은 가장 오래동안 참조되지 않은 페이지를 교체하는 알고리즘이다.
이를 위해서는 해당 페이지가 언제 참조되었는지를 기록해주어야 한다.
최근 참조를 1부터 시작해서 나아간다면, 페이지가 바뀔때마다 나머지 캐시에 있는 페이지들을 모두 +1씩 해주어야하는 번거로움이 있으므로,
그냥 time 이라는 변수를 만들어 캐시에 접근 할때마다 +1일 더해서 이 값을 그대로 써주었다.
이렇게 구현하면 time은 계속 늘어나므로, 가장 time값이 작은 페이지가 가장 오래동안 참조되지 않은 페이지가 된다.
캐시 자체는 계속 현재 도시이름이 캐시에 있는지 확인해주어야 하므로, 빠른 접근을 위해 딕셔너리를 사용했다.
캐시 크기가 0일 수도 있는데, 이 경우는 무조건 cache miss가 나니까 그냥 도시이름 크기에 5를 곱해주면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(cacheSize, cities):
answer = 0
cache = {}
time = 1
if cacheSize == 0:
return len(cities)*5
for city in cities:
city = city.lower()
if city in cache:
cache[city] = time
answer+=1
else:
if len(cache) < cacheSize:
cache[city] = time
else:
tmp = min(list(cache.values()))
for item in cache:
if cache[item] == tmp:
del cache[item]
cache[city] = time
break
answer+=5
time+=1
return answer