[프로그래머스/python/Lv2] 캐시

1. 코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > [1차] 캐시

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

프로그래머스

코드1

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    cache = deque()
    
    if cacheSize == 0:
        answer = 5*len(cities)
    else:
        for city in cities:
            city = city.lower() # 대소문자 구분X
            if city in cache: # cache hit
                answer+=1
                cache.remove(city)
                cache.append(city)
            else: # cache miss
                answer+=5
                if len(cache) >= cacheSize:
                    cache.popleft()
                    cache.append(city)
                else:
                    cache.append(city)
                    
    return answer

코드2

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

 

풀이

LRU를 직접짜는 문제

Least Recently Used 알고리즘

 

참고

https://rangsub.tistory.com/124

[Algorithm] LRU(Least Recently Used) 알고리즘