[프로그래머스/python] kakao 캐시

문제: cache 사이즈와 문자열 리스트가 주어졌을 때, 캐시 교체에 드는 총 실행시간을 구하는 문제입니다.

 

풀이 코드:

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

 

문제 풀이:

문제 풀이의 핵심은 maxlen 옵션을 활용한 deque 사용입니다.

문제에서 캐시 교체 알고리즘은 LRU 알고리즘을 활용한다고 명시해주었습니다.

 

예를 들면, 길이가 3인 ['a', 'b', 'c'] 라는 리스트에 'd' 라는 원소가 추가된다면 'a'라는 원소가 없어지고 'd'가 추가되는 것입니다.

deque의 maxlen 옵션을 활용한다면 위와 같이 동일하게 동작하는 deque를 구현할 수 있습니다.

from collections import deque

q = deque(maxlen=3)

for i in range(6):
    q.append(i)
    print(q)

위와 같은 코드가 있을 때, 데크에 담기는 원소를 확인해보면 다음과 같습니다.

 

따라서, 문제 풀이는 maxlen이 정의된 deque를 통해 풀어주었습니다. 

def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

maxlen이 설정된 deque에 append 할 경우, LRU 알고리즘과 맞게 동작하므로 원소가 있는지 여부만 판단하여 실행시간을 구해주었습니다.(원소가 있을 경우, 'cache hit'. 없을 경우, 'cache miss'.)

 

 

* 해당 문제는 https://www.youtube.com/watch?v=orf9ailzXvI 을 듣고 작성하였습니다.