[프로그래머스] 캐시 (python 파이썬)

문제

https://programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

 

풀이 및 소스코드

LRU(Least Recently Used)란, 최근에 사용한 것을 최상위 순위에 오래전에 사용한 것을 최하위 순위에 두고, 데이터가 하나 들어온다면 가장 오랫동안 사용하지 않은 것을 빼고 새로운 데이터를 넣는 방법이다.

 

먼저 cacheSize가 0일 때, 저장할 공간이 없으므로 len(cities)*5 를 return 해줘야 한다.

 

만약, city가 cache 안에 있다면 answer += 1 한 후에 city 를 cache의 오른쪽 끝에 오게끔 함으로써 우선순위를 높여준다.

cache는 아래와 같이 구성된다.

cache = [가장 먼저 나갈 것, *** , 가장 나중에 나갈 것(즉, 최근에 사용한 것)]

 

city가 cache 안에 없다면 cache의 얼마나 차있는지 확인해봐야 한다.

cache안에 있는 데이터의 양과 cacheSize가 같다면 가장 오래전에 사용한 데이터를 빼고 넣어줘야 한다.

def solution(cacheSize, cities):
    answer = 0
    cache = []
    if cacheSize == 0:
        return len(cities)*5
    for city in cities:
        city = city.upper()
        if city in cache: #city가 캐시안에 있다면
            answer += 1
            idx = cache.index(city)
            if idx != len(cache)-1: #가장 최근에 사용하지 않았다면 중간에 있을테니 맨 끝으로 보내줘야 한다.
                cache = cache[:idx]+cache[idx+1:]
                cache.append(city)
        else:
            answer += 5
            if len(cache) == cacheSize: 
                cache = cache[1:]
                cache.append(city)
            else:
                cache.append(city)
    return answer