LRU(Least Recently Used) 알고리즘:가장 사용한지 오래된 것을 내보내는 알고리즘
cache hit일 경우 실행시간은 1
cache hit = 이미 캐시에 있는 데이터가 다시 들어오는경우
cache miss일 경우 실행시간은 5
cache miss = 캐시에 없는 데이터가 들어오는 경우
각 도시 이름은 대소문자 구분 x
"""
입출력 예시)
cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] -> 50
cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] -> 21
cacheSize = 2, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] -> 60
cacheSize = 5, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] -> 52
cacheSize = 2, cities = ["Jeju", "Pangyo", "NewYork", "newyork"] -> 16
cacheSize = 0, cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"] -> 25
"""
def solution(cacheSize, cities):
answer = 0 # 실행시간
i = 0 # 초기 캐시 인덱스
cache = []
if cacheSize == 0: # 캐시 사이즈가 0인 경우
return len(cities)*5 # cache miss이므로 실행시간: len(cities)*5
for c in cities:
city = c.lower() # 도시 이름은 대소문자를 구분하지 않으므로 소문자로 통일
# city가 이미 캐시 메모리에 있는 경우
if city in cache:
cache.remove(city) # 캐시에서 해당 city 위치 변경
cache.append(city)
answer += 1 # cache hit -> 1
# city가 캐시 메모리에 없는 경우
else:
answer += 5 # cache miss -> 5
# 캐시에 빈 공간이 있는 경우(캐시의 인덱스가 캐시 사이즈보다 작을 때)
if i < cacheSize:
cache.append(city) # city를 캐시에 보관
i += 1 # 인덱스 + 1
# 캐시에 빈 공간이 없는 경우
else:
cache.pop(0) # 캐시에서 사용된지 오래된 city 빼기
cache.append(city) # 현재 city를 캐시에 보관
return answer
다른 풀이 -> deque 이용
def solution(cacheSize, cities):
import collections
cache = collections.deque(maxlen=cacheSize)
time = 0
for i in cities:
s = i.lower()
if s in cache:
cache.remove(s)
cache.append(s)
time += 1
else:
cache.append(s)
time += 5
return time
