[프로그래머스] 👨‍💻 캐시 - [1차] 2018 카카오 블라인드 채용 / Python

👨‍💻 캐시(cache) 문제 풀어보기

😃 나의 코드

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

우선 이 문제에서 사용 된 캐시 교체 알고리즘인 LRU(Least Recently Used) 알고리즘에 대해서 알아야 합니다. 캐시의 사이즈는 한정 되어있기 때문에 캐시 사이즈가 꽉 찬 상태에서 새로운 캐시를 넣으려면 기존 캐시에 있던 데이터를 교체해야하는 데 여기서 어떤 데이터를 교체할 것인가가 캐시 교체 알고리즘의 목적입니다. LRU 알고리즘은 직역하자면 가장 최근에 사용되지 않은 것 즉, 가장 오래전에 사용한 것을 제거하는 알고리즘입니다. 이 알고리즘의 기본적 가설은 오랫동안 사용하지 않았던 데이터는 앞으로도 사용할 확률이 적다는 것입니다.

cities = [city.lower() for city in cities]

위의 설명에 따라서 코드를 작성해보겠습니다. 우선 입력 형식에서 대소문자 구분을 하지 않는다라는 조건을 주었으니 문제를 단순화하기 위해 입력된 배열 속 문자열을 소문자로 바꿔줍니다. 리스트 축약(List Comprehension)을 통해 코드를 좀 더 간단히 했습니다.

이제 문제가 단순화되었으니 데이터를 받으며 캐시를 채워가는 과정을 진행합니다. 큰 분기는 cacheSize의 크기가 0인지 영이 아닌 지로 나눕니다. 0인 경우 모든 데이터가 cache miss로 판별되어 전체 도시 데이터 길이 * 5만큼 실행시간이 늘어납니다.

if city in cache:
	cache.pop(cache.index(city))
	cache.append(city)
	time += 1

다음은 0이 아닌 경우입니다. 0이 아닌 경우 캐시에 데이터를 채워가는 시행을 진행하게됩니다. 데이터를 넣는 경우에도 같은 도시 데이터가 이미 캐시 안에 있는 경우와 그렇지 않은 경우로 분기가 생깁니다. 같은 도시 데이터가 이미 캐시 안에 있는 경우 캐시에 있는 도시 데이터를 없에고 같은 도시 데이터를 cache 배열의 맨 뒤에 추가하고, cache hit이기 때문에 실행시간인 time에 1을 더해줍니다.

같은 도시 데이터가 캐시 안에 없는 경우에는 새로운 데이터를 캐시에 넣어야합니다. 따라서 이 경우에도 캐시가 꽉 찬 경우와 꽉 차지 않은 경우로 나눠서 확인합니다. 캐시가 꽉 찬경우 LRU 알고리즘에 따라 가장 오랫동안 쓰이지 않은 cache배열의 0번 index를 pop해줍니다. 그리고 새로운 데이터를 캐시 배열 맨 뒤에 추가해줍니다. 캐시가 꽉 차지 않은 경우에는 캐시의 교체 없이 새로운 데이터만 추가해줍니다. 이 경우 같은 도시 데이터가 캐시 안에 없는 cache miss이기 때문에 실행 시간 time에 5를 더해줍니다.

이렇게 계산된 실행시간 time을 반환하면 문제는 마무리됩니다.

Written with StackEdit.