2018 KAKAO BLIND RECRUITMENT - 캐시, 파이썬

1. 문제

 - 프로그래머스 링크 

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

2. 풀이 및 개선

 

- 캐시 교체 알고리즘은 LRU(Least Recently Used)을 구현하는 것이 핵심이다. 

- 시간제한도 널널하고 문제는 쉬운 편이다. 

- 다만 졸릴 때 풀어서 그런지 너무 비효율적으로 짰다. 

- 다른 코드를 보니 캐쉬 배열을 관리하면서 가장 오래된 캐쉬데이터를 pop(0)으로 빼주고 append로 최근 데이터를 넣어주는 식으로 구현하였다. 

 

3. 코드

def solution(cacheSize, cities):
    if cacheSize == 0 :
        return len(cities) * 5
    answer = 0
    cache = []
    used = []
    for i, city in enumerate(cities) :
        city = city.lower()
        if city not in cache :
            if len(cache) < cacheSize:
                cache.append(city)
                used.append(i)
            else :
                idx = used.index(min(used))
                cache[idx] = city
                used[idx] = i
            answer += 5
        else :
            idx = cache.index(city)
            used[idx] = i
            answer += 1
    return answer