[프로그래머스] 2018 Kakao - 캐시 (Python)

23 Apr 2021

문제

문제 : 2018 카카오 캐시
풀이 시간 : 23:15 ~ 23:32 (이제부터 시간 측정을 좀.. 해야할 것 같습니다)

생각하시는 대로 구현하면 됩니다. 제 경우에는 다음과 같이 구현했습니다.

city들의 최근 사용 시점을 저장할 recentUse dictionary를 선언합니다.

for city : cities로 순회하며

city를 소문자로 바꿔준다. (대소문자를 가리지 않기 때문)
recentUse[city]를 현재로 업데이트
cache hit과 cache miss 판별
- cache hit
  1. 현재 살펴보는 city가 cache에 이미 존재하는 경우
- cache miss
  1. caches의 길이가 cacheSize와 같을 때 : 캐시에서 삭제할 가장 오래전에 사용한 노드를 고르고, 해당 노드의 자리에 현재 city를 넣어줍니다.
  2. caches의 길이가 cacheSize보다 적을 때 : 그냥 넣어주면 됩니다.

구현

# 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