[Lv2] 캐시(python)

1. 문제

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

코딩테스트 연습 - [1차] 캐시

 

2. 접근 방법

- 문제에서 요구되는 캐시의 조건

   1) 사이즈가 정해져있다. 

   2) 특정 사이즈를 넘어가면 "가장 옛날에 삽입된" 대상을 지우고 새로운 대상을 삽입한다.

   => 도시들 간 순서가 있어야 함 & 자료구조의 사이즈를 알아야 함

   

- 초기 접근 방식

 딕셔너리를 사용해서 key - 도시 이름, value - 해당 도시가 들어왔던 직전 순서를 저장. i번째 도시를 찾으려고 할 때, 이미 이전에 값이 들어온 적이 있으면 해당 value 값을 보고 value >= i - cacheSize + 1이면 cache hit으로 봤음

 

- 초기 접근 방식의 반례 

cacheSize = 3, A B B B A 라 하면 , 마지막 A를 찾을 때 cache[A] = 0이 되어서 원래는 cache hit임에도 cache miss로 판정됨

=> " 절대적인 순서가 필요한 게 아니라 캐시 내의 상대적인 순서가 필요함 "

 

- 두번째 접근 방식 

 cache를 list로 정의 -> 이번에 들어오는 도시가 이미 있는 대상이면 해당 도시를 캐시 내에서 삭제 & 도시 이름을 list에 가장 앞에 삽입하고 (도시 간 순서 유지) -> 삽입 후 cache 크기가 cacheSize를 넘어가면 가장 마지막 요소 삭제 ( LRU )

 

3. 실수 한 것 & 새로 안 것 

1)  컨테이너형 자료구조 요소들 간 순서가 필요할 때 " 절대적인 순서"가 필요한지 "상대적 순서"가 필요한지를 잘 보기. 특히 자료구조의 크기가 제한적인 경우는 상대적 순서인지 잘 볼 것! 상대적 순서일 경우 list만으로도 풀이 가능

 

2) list내 가장 앞에 요소 삽입하기  : cache = [ city ] + cache

 

4. 코드

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