[PG/Python] 캐시

📌 문제

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

코딩테스트 연습 - [1차] 캐시

 

📌 문제 접근 방법

1. LRU (Least Recently Used) : 페이지 부재가 발생했을 경우 가장 오랫동안 사용되지 않은 페이지를 제거하는 페이지 교체 알고리즘
   
   위의 그림의 경우에는 캐시의 사이즈가 3이다.
   1) 1, 2, 3을 참조할 경우에 캐시에 빈 공간이 있기 때문에 캐시에 저장한다.
   2) 캐시가 이미 꽉찬 뒤, 다시 1을 참조할 경우 가장 오랫동안 참조되지 않은 순서를 갱신한다.
   3) 그 후 4와 5를 참조할 경우 캐시에 공간이 없으므로 가장 오랫동안 참조되지 않은 페이지를 제거 후 저장한다.
2. cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우
   cache miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우
3. 캐시의 사이즈가 0일 경우 cache miss만 발생하므로 cities의 길이에 5을 곱해서 바로 리턴한다.
4. 그 외의 경우는 LRU 알고리즘을 그대로 구현하면 되는데 '대소문자 구분을 하지 않는다'는 조건이 있으므로 city.lower()를 사용해서 city의 이름을 모두 소문자로 변경한 후 진행하였다.

​

📌 코드

from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5
    
    cache = deque()
    answer = 0
    
    for city in cities:
        city = city.lower()
        
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
        elif len(cache) < cacheSize:
            cache.append(city)
            answer += 5
        else:
            cache.popleft()
            cache.append(city)
            answer += 5
            
    return answer