1차 캐시→체크리스트X, OrderedDict()★★

나의 풀이 

from collections import OrderedDict
def solution(cacheSize, cities):
    #city가 cache에 없는 경우에는 전부다 cache miss이다.
    if cacheSize ==0:
       return len(cities)*5

    #cities의 요소를 저장하기 위한 cache공간으로 OrderedDict를 사용한다.
    cache=OrderedDict()
    

    #최초실행시간을 0으로 초기화한다.
    execution_time =0


    #대소문자를 구분하지 않으므로 전부다 대문자로 바꾸어 놓는다.
    for city in cities:
        city=city.upper()
   
    
    #만약에 city가 cache안에 있다면 cache hit이다.
        if city in cache:
            execution_time+=1
            #가장 최근에 사용했다는 것을 표시하기 위해 city를 OrderedDict의 끝으로 보낸다. 
            cache.move_to_end(city, last=True)
           

        #city가 cache안에 없다면 cache miss이다.
        #city가 cache안에 없는 경우: 애당초 없었던 경우, 꽉차서 없었던 경우
        else:
            execution_time+=5
            if len(cache)==cacheSize: #만약에 cache가 full이라면
                cache.popitem(last=False)  #last 가장 최근까지 사용함
                #LRU는 가장 오랫동안 사용되지 않는 데이터를 교체하는 정책이다.
                #따라서 last=False 가장 오랫동안 사용하지 않은 즉 가장 앞쪽에 있는 item을 pop한다.

            #city는 key이고 None은 value이다.   
            cache[city]=None
    

    return execution_time

▶ LRU (Least Recently Used)
       가장 오랫동안 사용되지 않은 데이터 교체


▶ OrderedDict()
    특이사항 : 삽입된 순서를 기억하고 있다. 

    삽인된 순서를 기억하고 있지 않다면, 엉뚱한 값을 뽑을 수 있는 경우가 발생한다. 

https://bio-info.tistory.com/52

[Python] Ordered dict 이란

 

 

 

 

▶ popitem()

▶ popitem 메서드의 default value는 last=True이기 때문에 그냥 popitem()을 사용하였을 때, 마지막 인자를 pop 합니다.

▶ popitem(last=False)를 실행하면 OrderedDict의 첫 번째 인자를 pop 하게 됩니다


▶ move_to_end(key, last=True)

▶ move_to_end 메서드의 default value는 last=True이기 때문에 그냥move_to_end을 사용하였을 때,

    해당 key에 해당하는 값을 마지막(끝)으로 옮긴다.

▶ move_to_end(key, last=False)를 실행하면 해당 key에 해당하는 값을 처음으로 옮긴다.