[Python] 파이썬 프로그래머스 캐시

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

프로그래머스

---

나의 풀이

LRU 알고리즘을 알아야 풀 수 있는 문제이다. 페이지 교체 알고리즘으로 LRU를 포함한 다양한 알고리즘이 존재한다.

LRU는 Least Recently Used로 가장 오랜 시간 사용되지 않은 페이지를 교체하는 방법이다.

• 캐시가 찼을 때 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요하다.
• 캐시의 크기가 3이라고 했을 때 3개의 페이지에 캐시가 들어있다면 맨 뒤에 있는 페이지를 지우고 새로운 페이지를 앞에 추가한다.
• Miss는 cache에 내가 찾는 데이터가 없을 때를 의미한다
• Hit은 cache에 내가 찾는 데이가 있을 때를 의미한다.

dequeue를 list로 구현하여 사용하였다.

---

def solution(cacheSize, cities):
    cache = list()
    answer = 0
    while cities:
        city = cities.pop(0)
        city = city.lower()


        if city in cache:
            answer += 1
            cache.pop(cache.index(city))
        else:
            answer += 5
        cache.append(city)
        if len(cache) > cacheSize:
            cache.pop(0)

    return answer

다른 사람의 풀이

 collections의 maxlen을 사용하였다. 이를 통해 chcheSize에 대한 추가적이 처리를 없애 시간이 단축된다.

maxlen은 최대 list의 길이를 지정하는 것으로 이 문제에 쓰기 적합하다.

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    print(cache)
    time = 0

    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time