[프로그래머스] 캐시 - Python

1. 문제 설명

캐시 크기와 도시이름들이 input으로 주어지고, 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

2. LRU 알고리즘이란?

캐시를 대체하는 방법 중 하나

운영체제에서 가상 메모리 관리를 위한 페이지 교체 알고리즘 중 하나

Least Recently Used Algorithm
→ 뜻 : 최근에 가장 적게 쓴

→ 최근에 가장 적게 쓴건 버리고, 새로나온 아이템을 넣고, 이런 방식으로 캐시를 운영하는 교체 전략 알고리즘

3. 코드

def solution(cacheSize, cities):
    cache = []
    time = 0

    for city in cities:
        city = city.lower() #도시이름의 대소문자 구분 x
        if city in cache:
            time +=1
            cache.remove(city) #기존 캐시 제거
            cache.append(city) #새롭게 캐시 넣어줌
        else:
            time +=5
            if cacheSize!=0:
                if len(cache) >= cacheSize: #새로운 캐시를 넣을 수 없는 상황이라면
                    cache.pop(0) #가장 오래된 아이템 삭제
                cache.append(city) #이번에 넣어야할 아이템을 캐시에 추가

    return time