[python]programmers-캐시

2018 KAKAO BLIND RECRUITMENT

문제 : 캐시

 

• 캐시사이즈와(cacheSize) 읽을 데이터(cities)를 주고 지금 읽는 데이터가 cache에 있으면(hit) 실행시간+1, 없으면(miss) 실행시간+5 를 해주어 최종 데이터를 읽는 시간이 얼마인지 알아내는 문제이다.
• 캐시 교체 정책은 LRU 방식을 이용한다.
• 만약 캐시에 [1, 2, 3]이 있고, 현재 1을 조회하려고 하면 hit이고(실행시간+1), 가장 최근에 조회된것은 1이다.
• 이때 4가 들어온다면, 1이 아닌 2가 제거되고 캐시에는 [3, 1, 4]가 남는다(운영체제를 배우지 않았다면 아마 헷갈릴수도 있을듯!)

 내 풀이

def solution(cacheSize, cities):
    time = 0
    cache = []
    if(cacheSize == 0) :
        return len(cities) * 5
    for i in cities :
        i = i.lower()
        if(i in cache) : 
            # print('hit')
            time += 1
            # hit_idx = cache.index(i)
            # cache = cache[:hit_idx] + cache[hit_idx+1:] + [i]
            cache.remove(i) # 그냥 remove를 써주자!
            cache += [i]
        else :
            # print('miss')
            time += 5
            if(len(cache) < cacheSize) :
                cache += [i]
            else :
                cache = cache[1:] + [i]
        print(f'cache : {cache}')
    return time

 

처음코드를 제출했을 때 두개의 테스트케이스를 통과하지 못했는데, 그 이유가 cacheSize가 0일때를 고려하지 못했기 때문이다.

만약 if(cacheSize==0)을 확인하는 if문이 없었다고 생각해보자

• cacheSize = 0, data = [1, 1]이 차례로 들어온다고 생각해보자(답은 10)
• data로 1이 들어온다. -> i가 cache에 없으므로 else문으로 들어간다(miss)
  • time+5
  • len(cache) (=0) < cacheSize (=0) 가 아니므로 else문에 들어가서 cache = [1]이 된다.
  • 일단 여기서 부터 말이안되는게 cacheSize가 0이므로(cache가 없으므로) cache에 data가 들어가면 안된다.
• data로 다시 1이 들어온다 -> i가 cache에 있으므로 if문으로 들어간다.(hit)
  • time+1
  • cache에는 다시 1이 저장되어 [1]이 된다.

cache가 0이라면 어떠한 데이터에 대해서 실행시간이 5가 추가되야된다.

 

테스트케이스 통과 후, 다른사람들의 풀이를 보며 조금 고친부분은 cache.remove(i)부분이다.

만약 캐시사이즈가 3이고, [1, 2, 3]이 있는경우 1을 조회한다고 해보자.

• 현재 캐시에 들어온 순서는 1, 2, 3이다.(가장최근에 3이 들어옴. 캐시에는 들어온 순서로 정렬하고 있음)
• 1이 다시 조회되었으므로 hit이고, 가장 최근에 접근한 순서는 2, 3, 1이 된다.
• 그러므로 원래 캐시 [1, 2, 3]에서 [2, 3, 1]이 되어야 한다.
• 따라서 원래 캐시에서 1을 지우고([2, 3]), 마지막에 1을 붙여준다.([2, 3, 1])

원래는 1의 인덱스를 찾아서 슬라이싱 해주었는데, 그냥 간단하게 cache.remove(1)해주고, cache += [1] 을 해주면 된다.