[Programmers] [2018 KAKAO BLIND RECRUITMENT] [Python] Level2_[1차]캐시

문제

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

프로그래머스

 

풀이

# 프로그래머스 2단계 - [1차] 캐시 
from collections import deque
def solution(cacheSize, cities):
    if cacheSize == 0: return 5 * len(cities)
    answer = 0
    cache = deque(maxlen=cacheSize)
    for city in cities:
        city = city.upper()

        if city in cache: # cahce hit
            cache.remove(city)
            cache.append(city)
            answer += 1
        else: # cache miss
            cache.append(city)
            answer += 5

    return answer

LRU 알고리즘을 알고 있었다면 매우 쉽게 풀 수 있었을 것이다. 

문제를 처음 봤을때 스택을 사용하려고 했는데 앞뒤의 삭제와 삽입이 O(1)인 데크를 떠올려서 이번 문제에 사용하였다.

일단 캐시 크기가 0이라면 값이 들어올때마다 캐시를 교체해야 하기 떄문에 도시의 수 * 걸리는 시간(5) 이다. 

그리고 캐시를 데크로 선언해주고 

입력으로 받을 값을 하나씩 비교하도록 한다.

첫번째 조건인 대소문자를 구별하지 않으므로  모두 대문자로 비교로 통일 하였다. 

그 후 만약에 입력값이 캐시 안에 존재한다면 기존의 값은 제거하고 덱의 맨 끝에 값을 추가해 준다.  

그리고 캐시 적중이라면 실행시간이 1이므로 더해준다. 

그 외의 경우 캐시 미스라면 덱의 끝에 값을 추가해준다. 

** 여기서 deque의 최대 길이를 cacheSize로 해두었으므로 else에서 굳이 비교를 하지 않아도 사이즈 크기를 넘어가면 맨 앞의 값이 빠지게 된다.