[프로그래머스] Lv2. 캐시

📝 문제

풀이

리스트 + 딕셔너리 활용한 풀이

단순히 in 사용하고 싶지 않아서 이렇게 풀었다. used는 딕셔너리로 키 값을 도시 이름으로 갖고, value 값으로는 참조 시기를 가진다. 참조 시기가 0이라면 현재 캐시에 존재하지 않는 것.

LRU 방식은 이 데이터가 언제 캐시에 추가되었었는지 사용된 시기를 기록해야 하는데 그 기록을 반드시 숫자로 해야 한다고 생각해서 이렇게 작성했다. 다른 풀이를 보니 이 방식말고 간단하게 그 데이터를 꺼냈다가 다시 뒤에 추가하는 방식으로 하면 가장 예전에 사용됐던 데이터가 자동으로 제일 앞에 위치해서 굳이 시기를 따로 기록해둘 필요가 없다.

def solution(cacheSize, cities):
    answer = 0

    used = dict()
    top = 0
    queue = [0] * cacheSize
    for idx, city in enumerate(map(lambda x: x.lower(), cities), 1):
        answer += 1
        
        # 도시 이름이 캐시에 존재할 때
        # 참조 시기만 업데이트
        if used.get(city):
            used[city] = idx
            continue

        # 도시 이름이 캐시에 존재하지 않지만 캐시가 비어 있을 때
        answer += 4
        if top != cacheSize:
            queue[top] = city
            used[city] = idx
            top += 1
            continue
        
        # 캐시 크기가 0이 아닐 때
        # 캐시를 돌면서 가장 예전에 사용됐던 도시 이름을 제거하고
        # 그 자리에 현재 도시 이름을 넣고 참조 시기 업데이트
        if queue:
            least, minValue = 51, 100001
            for header in range(cacheSize):
                if used[queue[header]] < minValue:
                    least = header
                    minValue = used[queue[header]]

            used[queue[least]] = 0
            queue[least] = city
            used[city] = idx

    return answer

deque와 maxlen을 활용한 풀이

deque의 maxlen 기능은 덱의 크기를 고정하고, 그 고정된 크기를 넘어서는 데이터가 들어오는 경우 가장 왼쪽의 데이터를 제거하는 방식이다.

가장 왼쪽의 데이터는 가장 오랫동안 사용되지 않은 데이터이므로 LRU 방식으로 진행될 수 있다.

def solution(cacheSize, cities):
    answer = 0
    cache = deque(maxlen=cacheSize)
    
    for s in cities:
        city = s.lower()
        
        # 도시에 캐시에 존재한다면 제거하고 새로 추가
        if city in cache:
            answer += 1
            cache.remove(city)
            cache.append(city)
        # 존재하지 않는다면 바로 추가
        # 자동으로 가장 왼쪽(가장 오랫동안 사용되지 않은)데이터가 삭제
        else:
            answer += 5
            cache.append(city)
    return answer

from collections import deque