[알고리즘] 프로그래머스 17680 캐시 파이썬

 

 

프로그래머스

 

 

 

 

 

# 2018 카카오 코딩테스트 기출

 

 

- 캐시 : 저장할 수 있는 공간

- 캐시 크기 3 == 3개의 문자열 저장 가능

 

- LRU : 가장 마지막으로 사용된 것을 교체하는 알고리즘

- 스택에 값을 저장하는데, 먼저 저장된 것부터 쌓이게 된다

- 스택에 존재하지 않아 기존의 것을 빼고 새로운 값을 저장해야 할 때는 popleft()로 가장 왼쪽의 값을 빼내고,

- 이미 스택에 존재하는 값일 경우 기존의 값을 remove 하고 새롭게 저장해준다

- deque의 pop()은 인덱스를 지정할 수 없어서 remove를 사용했다 

 

 

from collections import deque

def solution(cacheSize, cities):
    total = 0
    stack = deque([])
    
    # 저장소가 0일땐 한번에 곱함
    if cacheSize == 0:
        return len(cities) * 5
    
    for city in cities:
        city = city.lower() # 대소문자 구분X
        if city not in stack: # 캐시에 저장되어있지 않을 때
            total += 5
            if stack and len(stack) >= cacheSize: # stack에 값이 있는데 꽉 차있을 때
                stack.popleft() # 가장 왼쪽 (가장 오래된 것) 뽑음
            stack.append(city) # 새로 저장
            continue
        # 캐시에 저장된 도시일 때
        stack.remove(city) # 이미 저장된 도시를 빼서 새로 넣어줌
        stack.append(city)
        total += 1
    return total