[코딩테스트] 2018 KAKAO BLIND RECRUITMENT - 캐시

---

문제

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

프로그래머스

 

DB캐시를 적용해 성능 개선하는 문제

miss시에는 실행시간 5초, hit시에 실행시간이 1초일 때 LRU 알고리즘을 이용해 주어진 캐시크기로 캐싱하면 주어진 데이터들의 실행시간은?

 

 

 

---

전략

 

01. deque

 처음 문제를 읽고 나서 collections 라이브러리의 deque를 떠올렸다. deque에서 요소가 가득 차 있을 경우 가장 오래된 요소부터 축출되는 LRU(Least Recently Used)가 기본적으로 적용되어 있기 때문에 사용하기 편할 것 같았다. 1. maxlen파라미터에 캐시크기(cacheSize)를 넣어주고 2. for문으로 cities를 하나씩 읽어가면서 deque에 데이터가 있는지 검사한 뒤 3. 조건문으로 1초, 5초를 누적시켜주면 될 것 같다.

 hit된 경우 기존의 캐시를 삭제시켜주고 새로 업데이트 해줘야 하므로 그때는 O(n)의 시간복잡도가 있을 것 같다.

 

02. List

 그냥 리스트로 할 수도 있지 않을까? deque가 해주는 LRU 기능을 직접 구현해야 하고 나머지는 deque와 비슷할 것 같다. 근데 매번 리스트의 길이를 계산해줘야 해서 시간이 더 걸리지 않을까

 

03. OrderedDict or Dict

  검색할 때는 시간복잡도 O(1)의 이점이 있을 것 같다. 마찬가지로 딕셔너리의 크기를 매번 비교해주고 value값은 쓰지도 않을거라서 좀 낭비일 것 같다.

 

 

---

풀이

 

from collections import deque

def solution(cacheSize, cities):
    runtime = 0
    d = deque(maxlen=cacheSize)
    for city in cities:
        if city.lower() in d:
            runtime += 1
            d.remove(city.lower())
        else:
            runtime += 5
        d.append(city.lower())
    return runtime

 

 조건 중에 대소문자 구분을 하지 않는다고 했으므로 전부다 소문자로 변환해 통일시켜주기로 했다. 캐시인 d안에 city가 있을 경우 runtime에 +1을 해주고 캐시에서 해당 city를 업데이트해주기 위해 remove()메소드로 지운다. 없을 경우에는 runtime에 +5를 해준다.

 

 두 경우 다 city를 가장 최근 캐시에 추가해줘야 한다.