프로그래머스 level2 캐시

Problem

Solution

from collections import deque

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

# 캐시 사이즈 0<= <= 30
# LRU
# hit = 1
# miss = 5

현재의 도시가 캐시에 있는지 확인하여 있다면 제거 후 다시 넣어 맨 뒤로 넣었다.

만약 없는 경우 새롭게 넣어주고 캐시가 넘친다면 맨 앞에 있는 것을 popleft()하였다.

→ 캐시 hit하는 경우를 새롭게 append함으로써 hit되지 않은 도시들이 점점 deque의 앞쪽으로 이동하게 코드를 작성하였다.

다른 사람 풀이

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    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

deque의 maxlen을 이용하면 deque의 크기를 고정할 수 있다. append()를 하였을 때 캐시가 넘친다면 popleft()가 되고, appendleft()의 경우 pop()이 일어난다.

Reference

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