[프로그래머스] [1차] 캐시 python

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

출처 : 프로그래머스

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

---

코드

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

    return answer

풀이

LRU (Least Recently Used) 알고리즘

캐시 사이즈만큼 cities를 저장할 수 있다.

캐시 사이즈보다 작으면 캐시에 저장할 수 있고,

아니면 캐시에 있는 것을 빼야한다.

이 때, 최근에 사용하지 않은 ( 즉, 가장 사용 안하는 것) 것부터 캐시에서 제거한다. -> 그래서 큐를 쓴다.

 

찾는 데이터가 캐시에 있으면 cache hit

없으면 cache miss가 발생한다.

 

다만 이 문제는 캐시사이즈가 0일 때도 있다.

캐시사이즈가 0이면 모든 데이터에서 miss 가 발생해서 데이터 길이 * 5를 리턴해주면 된다.