[알고리즘] 프로그래머스 Lv2 캐시

문제

프로그래머스 문제 링크

풀이과정

LRU 알고리즘에 대한 사전 지식이 필요하다
본인은 아는게 없어서 검색을 했다.
LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법
이 블로그를 보고 hit, miss가 무엇인지 알고, 구현 알고리즘을 생각할 수 있었다.

단순하게 List의 pop, remove, append를 사용하여 구현했는데, 시간초과가 나지 않은 것은 운이라고 생각한다.
시간 효율을 고려하면 deque를 사용하는 것이 좋았을 것 같다.

코드

def solution(cacheSize, cities):
    cities = list(map(str.upper, cities)) # 도시 이름 전부 대문자로 만들어버림
    answer = 0
    cache = []
    for city in cities:
        if city not in cache: # 캐시 안에 없으면 miss이므로 +5
            cache.append(city)
            answer += 5
            if len(cache) > cacheSize: # 주어진 캐시 사이즈보다 크면 먼저 들어간거 삭제
                cache.pop(0)
        else: # 캐시 안에 있으면 hit이므로 +1
            cache.remove(city) # 캐시 내부에 있는 city 삭제 후, 뒤에 추가
            cache.append(city)
            answer += 1

    return answer

다른 사람의 풀이

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와 deque의 maxlen 인자를 사용하여 깔끔하게 구현한 풀이이다.