[프로그래머스/Programmers] [1차] 캐시 - Python

Link

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

 

Solution

[ Paging Algorithms ]

1. FIFO: cache에 들어온지 가장 오래된 페이지 교체
2. LRU: cache에서 가장 오랫동안 사용하지 않은 페이지 교체
3. LFU: cache에서 사용 빈도가 가장 적은 페이지 교체

from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5

    answer = 0

    cache = deque()

    for i in range(len(cities)):
        t = cities[i].lower()

        if t in cache:
            answer += 1
            cache.remove(t)
        else:
            answer += 5
            if len(cache) == cacheSize:
                cache.popleft()

        cache.append(t)

    return answer

🔑 key point: Paging Algorithm

 

Other Solution

해당 풀이는 필자의 풀이와 유사하지만 deque에 maxlen을 사용하여 불필요한 과정을 제거하였다.

maxlen의 간단한 사용예시를 첨부하니 참고바란다.

from collections import deque

a = deque([1,2,3], maxlen=3)
print(a)
a.append(4)
print(a)

<output>
deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)

from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5

    answer = 0

    cache = deque(maxlen=cacheSize)

    for i in cities:
        s = i.lower()

        if s in cache:
            cache.remove(s)
            answer += 1
        else:
            answer += 5

        cache.append(s)

    return answer

🔑 key point: Paging Algorithm
📌 Tip: deque(maxlen=cacheSize)