[Python] 프로그래머스 Level 2 [1차] 캐시 , LRU 알고리즘

LRU(Least Recently Used Alogorithm) 알고리즘

• 가장 오랜 시간동안 사용하지 않은 페이지를 교체하는 알고리즘
• 캐시 교체 정책(Cache Replacement Policy) 중 하나 - 이외에 FIFO(First In First Out), LFU(Least Frequently Used)
• Cache Hit : 참조하려고 하는 메모리가 캐시에 있는 경우
• Cache Miss : 참조하려고 하는 메모리가 캐시에 없는 경우

def solution(cacheSize, cities): # 캐시크기, 도시이름 -> 총 실행시간 출력
    answer = 0
    # LRU : 가장 오랜 시간동안 사용하지 않은 페이지 교체 알고리즘
    # hit : 참조하려고 하는 메모리가 캐시에 있는 경우
    # miss : 참조하려는 메모리가 캐시에 없는 경우
    
    cache = []
    
    if cacheSize == 0:
        return len(cities)*5
    
    for x in range(len(cities)):
        current = cities[x].lower()
        if current in cache: # 캐시 안에 있는 경우
            answer += 1
            cache.remove(current)
            cache.append(current)
        else: # 캐시 안에 없는 경우
            if len(cache) == cacheSize:
                cache.pop(0)
            cache.append(current)
            answer += 5
    return answer