[programmers/Lv.2] [1차] 캐시

❓  문제

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

 

🛎️  아이디어

1. 캐시 교체 알고리즘인 LRU를 구현하기 위해 deque를 사용한다.

2. 도시 이름을 하나씩 가져온다.
    a. 만약 deque안에 있으면(hit) 제거 후 time += 1
    b. deque안에 없으면(miss) 가장 왼쪽 요소 제거 후 time += 1 (LRU가 가장 오래된 요소를 제거하기 때문)

3. 해당 도시를 큐에 넣어준다.

** cache가 0인 경우 예외 처리가 필요함. -> hit인 경우가 없기 때문에 city개수 * 5를 리턴한다.

 

💻  풀이

from collections import deque

def solution(cacheSize, cities):
  if cacheSize == 0:
    return len(cities) * 5

  time = 0
  cache = deque([0 for i in range(cacheSize)])

  for city in cities:
    city = city.lower()
    if city in cache:
      cache.remove(city)
      time += 1
    else:
      cache.popleft()
      time += 5
    cache.append(city)
  return time