[Programmers] 캐시

출처: 프로그래머스 코딩 테스트 연습
https://programmers.co.kr/learn/courses/30/lessons/17680

LRU 알고리즘 (Least Recently Used Algorithm)

• 가장 오랫동안 사용되지 않은 페이지 제거
• cache hit : 참조값이 이미 캐시에 존재하므로 최근 위치로 갱신
• cache miss : 참조값이 캐시에 없으므로 가장 먼저 들어온(오래된) 참조값을 제거하고 현재값을 캐시에 넣어줌

📝 풀이 (python3)

def solution(cacheSize, cities):
    if cacheSize == 0: # 캐시 사이즈가 0일 때는 모두 cache miss
        return len(cities) * 5
    cities = [city.lower() for city in cities] # 대소문자 구분이 없으므로 소문자로 통일
    cache = []
    time = 0
    for city in cities:
        if city not in cache: # cache miss인 경우
            if len(cache) < cacheSize: 
                cache.append(city)
            elif len(cache) == cacheSize: # cacheSize만큼 채워진 경우에 가장 먼저 들어온 것은 나가고 새로운 city 추가
                cache = cache[1:] + [city]
            time += 5
        else: # cache hit인 경우 LRU이므로 이미 들어와있는 city를 맨 뒤로 정렬 
            cache.remove(city)
            cache.append(city)
            time += 1
    return time