프로그래머스 | 2018 KAKAO BLIND RECRUITMENT | [1차] 캐시 [파이썬 python]

프로그래머스

 

코드

def solution(cacheSize, cities):
    cache = [] # 캐시
    time = 0 # 총 실행시간
    if cacheSize > 0:
        for city in cities:
            city = city.lower()
            if city in cache: # 캐시에 존재할 때(cache hit) 최근 위치로 갱신
                cache.remove(city)
                cache.append(city)
                cache = cache[-cacheSize:]
                time += 1
            else: # 캐시에 존재하지 않으면(cache miss)
                cache.append(city)
                cache = cache[-cacheSize:]
                time += 5        
        return time
    
    else:
        return len(cities) * 5

페이지 교체 알고리즘에 대해 알고 있으면 쉽게 구현할 수 있는 문제이다.

LRU(Least Recently Used) 알고리즘은 새로운 페이지가 들어왔을 때 가장 오래 참조되지 않은 페이지를 교체하는 알고리즘이다.

따라서, 주어진 cities의 요소들을 하나씩 가져와 캐시에 해당 데이터가 존재하는지 확인한 후, 없으면 가장 오래 참조되지 않은 페이지와 교체하면 된다.

만약 캐시에 존재하는 데이터이면, 가장 최근 위치에 저장시켜 주면 된다.

이때, 캐시에 메모리가 존재하는 데이터일 때를 Cache Hit(캐시 히트)라 하고, 캐시에 메모리가 존재하지 않을 때를 Cache Miss(캐시 미스)라 한다.

 

문제에서 주어진 예시 중 하나인 cacheSize=5, cities=["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]의 과정은 다음과 같다.

cities의 요소를 하나씩 가져와 캐시에 존재하는지 확인하고 존재하면(cache hit) 실행시간에 +1, 존재하지 않으면(cache miss) +5 해준다.

cache hit은 위그림에서 7번째 S와 11번째 R의 경우에 발생했으며 이때는, 해당 데이터를 가장 최근 위치로 바꿔준다.

나머지는 모두 cache miss이다. 

cache가 가득 찼을 때(San 이후)는 가장 오래 참조되지 않은 데이터를 캐시에서 지우고, 새로운 데이터를 추가해 주면 된다.

 

캐시 크기는 정해져 있으므로 해당 크기를 유지하기 위해 슬라이싱을 사용하였다.

가장 최근 cacheSize개를 캐시에 유지하기 위해 cache[-cacheSize:]로 뒤에서부터 cacheSize를 남겼다.

if city in cache: # 캐시에 존재할 때(cache hit) 최근 위치로 갱신
    cache.remove(city)
    cache.append(city)
    cache = cache[-cacheSize:]
    time += 1
else: # 캐시에 존재하지 않으면(cache miss)
    cache.append(city)
    cache = cache[-cacheSize:]
    time += 5

맨 앞에 위치한 요소를 없애주는 pop 함수를 사용할 수도 있다.

cache.pop(0)

 

정확한 이유는 모르겠지만 cacheSize를 구분해주지 않으면 제출 시 2개의 테스트케이스에서 실패한다.

구분해주지 않아도 문제에서 주어진 예시에서 cacheSize=0인 경우도 통과했기 때문에 반례를 알 수가 없다.. 

그러므로 cacheSize가 0일 때와 0 이상일 때를 구분해서 조건문으로 세워주면 된다.