[파이썬] 캐시 - 2018 KAKAO BLIND RECRUITMENT [CODING TEST #23]

https://school.programmers.co.kr/learn/courses/30/lessons/17680

 

 

LRU나, Cache hit나, Cache miss? 문제를 한참동안 살펴봤다. 처음 들어보는 것들이기는 한데 원래 카카오가 설명을 안해주던가??

참다 참다 검색해봤는데, 별건 아니었다. 한 번 본 단어들은 Cache에 저장되고, 이후 들어오는 단어가 Cache에 있으면 실행 시간이 단축되고 그 단어가 Cache의 가장 앞으로 오는 알고리즘이 LRU이다.

새로운 도시가 들어오면 가장 나중에 들어온 도시가 Cache에서 빠져야 된다. 근데 리스트는 맨 앞의 원소를 빼는 게 없으니 큐를 이용하였다.   

검색해서 찾아보니 list.pop(index) 함수를 이용해서 리스트 내 원하는 인덱스의 원소를 뺄 수 있다. 또 배워갑니다.

 

캐시 사이즈가 0일 때는 간단하게 5 * 도시 수를 리턴하게 하였다.

 

from collections import deque
def solution(cacheSize, cities):
    cache = deque() # 최근 : append / 오래된 것 : popleft
    time = 0
    if cacheSize == 0: # cacheSize가 0이면 매 실행시간은 5
        return 5 * len(cities)
    
    for city in cities:
        city = city.lower() # 대소문자 구분 없음
        if city in cache: # cache hit! city를 맨 앞으로. 
            time += 1
            cache.remove(city)
            cache.append(city)
        else: # cache miss! city를 추가.
            time += 5
            if len(cache) == cacheSize: # cache 꽉 찼으면 오래된 캐시 제거.
                cache.popleft()
            cache.append(city)
    return time

 

요 아래는 큐를 쓰지 않은 버전. 이게 더 깔끔하고 나은 것 같다.

 

def solution(cacheSize, cities):
    cache = [] # 최근 : append / 오래된 것 : popleft
    time = 0
    if cacheSize == 0: # cacheSize가 0이면 매 실행시간은 5
        return 5 * len(cities)
    
    for city in cities:
        city = city.lower() # 대소문자 구분 없음
        if city in cache: # cache hit! city를 맨 앞으로. 
            time += 1
            cache.remove(city)
            cache.append(city)
        else: # cache miss! city를 추가.
            time += 5
            if len(cache) == cacheSize: # cache 꽉 찼으면 오래된 캐시 제거.
                cache.pop(0)
            cache.append(city)
    return time