Programmers / 2단계 / 캐시 / python

 

코딩테스트 연습 - [1차] 캐시 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

나의 풀이 

.

 

 

모범 답안

def solution(cacheSize, cities):
    cache = []
    time = 0
    for city in cities:
        city = city.lower()
        if cacheSize:
            if not city in cache:
                if len(cache) == cacheSize:
                    cache.pop(0)
                cache.append(city)
                time += 5
            else:
                cache.pop(cache.index(city))
                cache.append(city)
                time += 1
        else:
            time += 5
    return time

 

LRU : 가장 오랫동안 참조되지 않은 페이지를 교체

LRU 예시) 캐시크기: 2, 도시이름: [Jeju, Pangyo, NewYork, newyork]

1. Jeju가 들어온 경우, 참조리스트에 아무것도 없으므로 +5를 하고 buffer에 Jeju 삽입
   • buffer = ['Jeju'] , answer = 5
2. Pangyo가 들어온 경우, 참조리스트에 Jeju가 있으나 Pangyo가 아니므로 +5를 하고 Pangyo를 삽입
   • buffer = ['Jeju', 'Pangyo'], answer = 10
3. NewYork가 들어온 경우, 참조리스트에 NewYork가 없으므로 +5를 하고 참조리스트가 캐시크기 2보다 크므로 가장 오래전에 참조된 Jeju를 삭제하고 NewYork를 삽입
   • buffer = ['Pangyo', 'NewYork'], answer = 15
4. newyork가 들어온 경우, 참조리스트에 NewYork가 있으므로 +1를 하고 기존의 NewYork의 우선순위를 가장 높은 순서로 변경(리스트의 맨 마지막, 위의 경우는 이미 가장 높은 참조순위이므로 순서의 변경이 없음)
   • buffer = ['Pangyo', 'NewYork'], answer = 16

출처: https://eda-ai-lab.tistory.com/503 [TEAM EDA:티스토리]

 

 

 

LRU 알고리즘 개념

강생강의 하루 :: [Python] LRU(Least Recently Used) 알고리즘 (tistory.com)

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