프로그래머스 - [1차] 캐시 (2018 KAKAO BLIND)

문제 설명

제한사항 및 입출력

풀이

사실 LRU를 LFU로 착각하고 풀이하다가 이상함을 느끼고 고쳤다... 문제를 똑바로 읽자

별다른 알고리즘은 없는 것 같고 큐를 이용한 구현 문제인 것 같다. 주어진 캐시 크기만큼 배열을 유지해주면서 구현해주었다.

내 코드

from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return 5 * len(cities)

    ans = 0
    cache = deque([])
    for city in cities:
        # 대소문자 구분 없으니까 정규화
        city = city.lower()

        if city in cache:
            ans += 1
            cache.remove(city)
            cache.append(city)
        else:
            ans += 5
            if len(cache) == cacheSize:
                cache.popleft()

            cache.append(city)
            
	return ans

deque을 이용해서 popleft 하는 과정을 조금이나마 최적화해주었다. 일반적인 배열에서 첫 번째 원소를 제거하는 연산은 O(n)의 시간이 들기 때문에 첫 번째 원소 연산이 O(1)인 deque을 사용하여 풀이했다.

 

시간 복잡도는 모든 cities를 순회하면서 캐시를 순회하며 삭제, 추가해주기 때문에 O(n * m) - n: cities의 크기, m: 캐시의 크기이다.

고찰

아무리 생각해도 remove 연산이 너무 거슬려서 최적화할 수 있는 방법이 없을까 고민하다가 파이썬의 OrderedDict라는 자료구조를 발견했다! 순서를 조작할 수 있는 해시맵이라고 한다. OrderedDict를 사용하면 자연스럽게 마지막 캐시가 가장 마지막으로 사용한 캐시가 되기 때문에 remove해주는 과정이 O(1)로 줄어든다.

# OrderedDict 사용

from collections import OrderedDict

def solution(cacheSize, cities):
    if cacheSize == 0:
        return 5 * len(cities)

    ans = 0
    cache = OrderedDict()

    for city in cities:
        city = city.lower()

        if city in cache:
            ans += 1
            # 가장 마지막 삽입된 원소로 취급
            cache.move_to_end(city)
        else:
            ans += 5
            if len(cache) == cacheSize:
            	# 가장 처음 삽입된 원소 삭제
                cache.popitem(last=False)
            cache[city] = True

    return ans

 

시간 복잡도: O(n)