[파이썬] 프로그래머스 [1차] 캐시 풀이

문제 확인

프로그래머스

나의 풀이

• LRU : 가장 오랫 동안 참고되지 않은 캐시부터 제거하는 알고리즘
• LRU를 사용하려면 사용 순 → 입력 순으로 정렬하는 캐시가 필요하다. 

# LRU : 최근에 사용되지 않은 캐시부터 교체
# 사용 순 -> 입력 순으로 정렬 필요
from collections import deque

def solution(cacheSize, cities):
    # 실행 시간
    answer = 0
    cache = deque()
    for city in cities:
        # 대소문자 구분 X
        city = city.lower()
        # 캐시에 city 정보가 있다면
        # 다시 맨 뒤로 보냄
        if city in cache:
            answer += 1
            cache.remove(city)
        else:
            answer += 5
        # 새로운 도시 캐싱
        if cacheSize != 0:
            cache.append(city)
            if len(cache) > cacheSize:
                cache.popleft()
    return answer

다른 사람 풀이

• deque의 maxlen 인자를 활용하면, 굳이 길이를 확인하지 않아도 된다.

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

 

프로그래머스