문제 링크

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

문제 설명

• 캐시 사이즈, 입력 순서 주어짐
• LRU 알고리즘 수행 시간 리턴
• cache hit는 1초, cache miss는 5초 소요됨

풀이

• 큐와 집합으로 구현

코드

from collections import deque


def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    q = deque()
    visited = set()
    count = 0
    for city in cities:
        city = city.upper()
        # 캐시에 존재
        if city in visited:
            # 제거
            tmp_q = deque()
            while q:
                curr = q.popleft()
                if curr != city:
                    tmp_q.append(curr)
            # 추가
            tmp_q.append(city)
            q = tmp_q
            count += 1
        # 캐시에 없음
        else:
            # 초과할 경우 제거
            if len(q) + 1 > cacheSize:
                visited.remove(q.popleft())
            # 추가
            visited.add(city)
            q.append(city)
            count += 5
    return count