알고리즘 개요
- 캐시 크기(cacheSize)와 도시이름 배열(cities)를 입력 받는다.
- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다.
- 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.
조건
- 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
- cache hit일 경우 실행시간은 1이다.
- cache miss일 경우 실행시간은 5이다.
LRU
- 말 그대로 가장 오래된 페이지를 교체하는 알고리즘
- 자료구조의 큐(Queue)와 같이 선입 선출의 형태를 띄고 있다.
cache hit
cache miss
- 참조하고자하는 메모리가 캐시에 존재하지 않는 경우
알고리즘 풀이
def solution(cacheSize, cities):
cache = []
time = 0
for city in cities:
city = city.lower()
if cacheSize:
if not city in cache:
if len(cache) == cacheSize:
cache.pop(0)
cache.append(city)
time += 5
else:
cache.pop(cache.index(city))
cache.append(city)
time += 1
else:
time += 5
return time
- cache라는 빈 배열을 만든다.
.lower(): city는 대소문자를 구별하지 않으므로 for문을 돌며 cache 배열에 접근할 때 모두 소문자로 변경하여 저장한다.- cacheSize가 0인 경우에는 cache에 저장이 불가능 하므로 cache miss만 발생하여 매번 실행 시간이 5초가 되어 time에 5를 계속 더해준다.
- cacheSize가 1 이상인 경우, cache hit인지 cache miss인지 판별을 해야 하므로 cache에 city가 존재하는지 확인해야 한다.
- cache miss인 경우, 먼저 cacheSize와 cache의 길이가 같은 지 확인한다. 만약 같다면 더 이상 cache에 저장할 용량이 없다는 뜻으로
cache.pop(0)으로 cache의 첫 번째 값을 제거한다. 이후, cache에 cache.append(city)로 city를 저장한다. 실행 시간은 5초이므로 time에 5를 더한다.
- cache hit인 경우, 이전에 같은 이름의 city가 존재하므로 이는 가장 최근에 참조 되었다는 의미가 되므로 cache에 있던 city를 삭제한 뒤, 맨 뒤에 city를 다시 저장한다. 실행 시간은 1초이므로 time에 1을 더한다.
