코딩테스트 연습 - [1차] 캐시

DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

# 정답 코드

모든 조건을 만족시키는 코드를 한번에 짜지 않고 분할정복하듯이 구현해봤다. 처음엔 모두 정상적인 데이터일 경우 캐시 안에 데이터가 있으면 +1, 없으면 +5를 하였다.
cacheSize가 0인 경우는 저장을 아예 않기 때문에 예외처리하였다. 여기까지 한 후 문제의 조건을 추가로 처리하였다.
LRU(Least Recently Used)방식으로 구현하기 위해 찾는 데이터가 캐시안에 있을 때 맨 오른쪽으로 보내 왼쪽부터 가장 오래된 순으로 정렬되도록 구현하였다.

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    cache = deque([])
    for city in cities:
        city = city.upper()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
            continue
        if cacheSize == 0:
            answer += 5
            continue
        if len(cache) == cacheSize and cacheSize > 0:
            cache.popleft()
        cache.append(city)
        answer += 5
    return answer

# 참고 코드

문제를 이해하고 푸는데에는 그렇게 어렵지 않았지만 이 사람의 코드가 인상깊었다. deque는 옵션으로 maxlen을 설정할 수 있다! maxlen을 설정하면 그 이상의 데이터가 들어올 때 데이터를 밀어낸다.
append()을 하게 되면 맨 왼쪽의 원소가 삭제되고 맨 오른쪽의 값이 추가되고, appendleft()를 할 경우 맨 오른쪽의 원소가 삭제되고 맨 왼쪽에 값이 추가된다.

from collections import deque
def solution(cacheSize, cities):
    cache = 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