문제
-
문제 : 2018 카카오 캐시
-
풀이 시간 : 23:15 ~ 23:32 (이제부터 시간 측정을 좀.. 해야할 것 같습니다)
생각하시는 대로 구현하면 됩니다. 제 경우에는 다음과 같이 구현했습니다.
city들의 최근 사용 시점을 저장할 recentUse dictionary를 선언합니다.
for city : cities로 순회하며
- city를 소문자로 바꿔준다. (대소문자를 가리지 않기 때문)
- recentUse[city]를 현재로 업데이트
- cache hit과 cache miss 판별
- cache hit
- 현재 살펴보는 city가 cache에 이미 존재하는 경우
- cache miss
- caches의 길이가 cacheSize와 같을 때 : 캐시에서 삭제할 가장 오래전에 사용한 노드를 고르고, 해당 노드의 자리에 현재 city를 넣어줍니다.
- caches의 길이가 cacheSize보다 적을 때 : 그냥 넣어주면 됩니다.
- cache hit
구현
# 23:15 ~ 23:32
def solution(cacheSize, cities):
time = 0
recentUse = {}
caches = []
if cacheSize == 0 :
return 5*len(cities)
for idx, city in enumerate(cities) :
city = city.lower() # 대소문자 구분을 하지 않음!
recentUse[city] = idx
if city not in caches :
time += 4 # cache miss
if len(caches) == cacheSize : # 반드시 바꿔야하는 상황
lastUsed = idx # idx일리 없으므로 MAX값으로 넣음.
deleteDataIdx = 0
for idx, cache in enumerate(caches) :
if lastUsed > recentUse[cache] :
deleteDataIdx = idx
lastUsed = recentUse[cache]
caches[deleteDataIdx] = city
else : # 캐시에 더 들어갈 수 있음. 그냥 넣으면 됨.
caches.append(city)
time += 1
return time