파이썬 Python KAKAO_2018 캐시

링크 : 코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr) , LRU Cache Algorithm 정리 :: Jins' Dev Inside (tistory.com) , [프로그래머스] 캐시 / 2018 카카오 블라인드 1차 / 파이썬 (tistory.com)

문제에 대한 설명은 링크를 참조하는것이 좋을것같다. 

일단 LRU에 대한 기본개념을알아야하는데.. 

가장 최근에 사용된 항목은 리스트의 맨 앞에 위치하고 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다.

LRU 알고리즘의 구현은 Linked List 를 이용한 Queue 로 이루어지고, 접근의 성능 개선을 위해 Map 을 같이 사용한다.

중요한점 ! 가장 최근에 사용한 항목은 리스트의 맨 앞에 위치하고, 큐 속에 가장 오래된녀석이 다음번의 교체대상이되는것. 

 

처음 문제를 풀 땐 Queue에 대해 조금 방심하고, heap을 사용해도 되지않을까? 라고 생각했었다.. 

solution함수에서는 cache를 준비하고, city별로 연산을 진행한다. 
그리하여 findNidx라는 함수를 통해서 큐내부의 프로그램 마지막 사용시간을 -1씩 업데이트하고, 원하는 city가 있다면 해당 인덱스를 저장, 해당 사용시간 0으로 초기화를 진행
이후 리스트끝까지 돌고, city인덱스 return (city 없다면 -1) 방식을 사용했다. 

그리하여 인덱스 -1이 리턴되면  cache에 연산을 진행해주고, 
[-사용시간, 도시이름] 을 담은 heap을 사용했으며, 그렇기에 heappop하면 가장 오래된 (가장작은값) 녀석이 나오고 
 인덱스 -1이 아니라면 hit처리를 하는것으로 진행. 

import heapq
def findNidx(lru, city):
    idx=-1
    for i,v in enumerate(lru):
        lru[i][0]-=1
        time,ct = v
        if ct==city:
            idx = i
            lru[i][0]=0
    return idx

def solution(cacheSize, cities):
    answer = 0
    if cacheSize:
        lru = [[0,i] for i in range(cacheSize)]
        for city_ in cities:
            city=city_.lower()
            idx = findNidx(lru,city)
            if idx == -1: # Not in Cache
                print(lru, 'NOhit', city)
                answer+=5
                heapq.heappop(lru)
                heapq.heappush(lru,[0,city])
            else: # In Cache
                print(lru, 'hit', city)
                answer+=1
        return answer
    else:
        return 5*len(cities)

 

어느부분에서 잘못된건지를 모르겠다.. 

캐시사이즈 0 처리와, 동일한것들만 들어오는것, 등등 몇가지 예외를 생각해봤지만.. 도저히 모르겠다..

 

공부해볼만한 코드 deque의 maxlen이라는 옵션을 사용했다..!

# 공부할코드
def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        print(i,'\n',cache)
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time
cacheSize, cities=5,["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]#52
solution(cacheSize, cities)