[1차] 캐시 (2018 KAKAO BLIND RECRUITMENT) - 파이썬

def solution(cacheSize, cities):
    answer = 0
    cache = []
    
    for city in cities :
        city = city.lower()
        # Miss
        if city not in cache:      
            if cacheSize != 0:
                if len(cache) < cacheSize:
                    cache.append(city)
                else:
                    cache.pop(0)
                    cache.append(city)
            answer += 5
        # Hit!
        else:
            cache.pop(cache.index(city))
            cache.append(city)
            answer += 1
    return answer

문제요약

LRU(캐시교체 알고리즘) 을 사용하여 실행시간을 구하라.

설명

캐시교체 알고리즘은 아래를 참고하자.

https://smhope.tistory.com/572

 

 

1. 준비

    for city in cities :
        city = city.lower()

도시는 대소문자를 구분하지 않는다.

따라서 전부 소문자로 생각하고 처리해줄 것이다.

 

2. Miss (CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않을 때)

        # Miss
        if city not in cache:      
            if cacheSize != 0:
                if len(cache) < cacheSize:
                    cache.append(city)
                else:
                    cache.pop(0)
                    cache.append(city)
            answer += 5

도시가 cache에 존재하지 않을 경우 들어오는 분기점이다.

 

cache가 존재하지 않을 경우는 다음과 같다.

1) size가 0이기 때문에

2) 아직 들어온 적이 없기 때문에

 

size가 0인 경우에는 따로 처리할 것 없이 그냥 실행시키면 된다. 따라서 cacheSize != 0  을 넣어 처리해준다.

 

만약 사이즈가 0이 아니면 추가를 시키되 만약 허용되는 사이즈를 넘으면 안쓴지 제일 오래된 녀석을 지우고, 새로드러온 녀석을 넣어준다. (이게 LRU이다.)

 

그리고 실행시간을 5로 넣어준다.

 

2. Hit (CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우)

        # Hit!
        else:
            cache.pop(cache.index(city))
            cache.append(city)
            answer += 1

hit의 경우에는 cache에 도시가 들어가 있다는 뜻으로, 그 부분을 지우고 제일 최신부분에 넣어준다.