[프로그래머스] 캐시 문제풀이 python

🐒 문제

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

✍ 나의 풀이

from collections import deque

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

deque을 이용해 큐로 캐시를 구현하였다.

---

🧠 문제 이해

문제에서 주석이나 예제가 부족해서 이해가 조금 어려웠는데

예제들을 따라가보니

cities 리스트를 돌면서

캐시에 없는 도시면 answer += 5
캐시에 있는 도시면 answer += 1

을 해주는 것이다.

캐시에 값을 넣는 규칙은
현재 보고있는 도시이름이 캐시에 없을때, 캐시에 도시이름을 넣고,
캐시 길이가 cacheSize를 초과하면 캐시에서 마지막에 넣었던 값을 제거한다.

그런데 문제조건에

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

라고 명시되어있는데,

최근 캐시에서 호출된 도시이름을 캐시의 최상위로 옮긴다라고 이해하면 될 것 같다.

---

처음 코드 (오답)

from collections import deque

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

테스트케이스 11,15,18,19,20 에서 오답이 나와서 머리를 굴리다가

문제조건에

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

라는 구절을 보고
문제에서 요구하는 캐시는 캐시에서 값이 호출되면 캐시의 최상위로 올라오는게 아닐까 싶어서 코드를 수정했다.

두번째 코드 (정답)

from collections import deque

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