[프로그래머스] (1차) 캐시

문제 설명

프로그래머스 레벨 2의 문제로 2018 KAKAO BLIND RECRUITMENT  문제입니다. LRU 알고리즘을 안다면 쉽게 해결할 수 있는 문제입니다.

위의 문제를 통해서는 쉽게 이해하지 못합니다

 

LRU 알고리즘을 사용하는 문제임을 알 수 있습니다.

 

LRU 알고리즘에 대한 설명은 아래의 링크를 통해 확인할 수 있습니다.

[알고리즘] LRU(Least-Recently-Used) 알고리즘

 

풀이

def solution(cache_size, cities):
    cache = []
    time = 0

    for city in cities:
        city = city.lower()
        if city in cache:
            time += 1
            cache.remove(city)
            cache.append(city)
        else:
            time += 5

            if cache_size == 0:
                continue

            if len(cache) >= cache_size:
                cache.pop(0)

            cache.append(city)

    return time

 

변수 설명

cache: 캐시로 city 정보를 담습니다.

time: 소요된 시간을 계산합니다.

cache_size: 캐시의 크기입니다.

 

간단 설명

LRU 알고리즘만 안다면 쉽게 풀 수 있는 문제입니다. 전체 도시들을 순회하며 모두 소문자로 바꾼 후 알고리즘을 진행합니다. (대소문자 구분 X)

 

만약 cache에 도시가 있다면 time을 1증가하고 도시를 cache의 가장 앞으로 넣습니다.

도시가 cache에 없고 cache가 용량을 넘었다면 가장 오래된 cache의 데이터를 삭제합니다. 그 후 도시를 cache에 삽입합니다.

 

이 문제는 LRU 알고리즘만 안다면 레벨1의 문제라고 할만큼 간단한 문제입니다.