프로그래머스 [1차]캐시 - level2 [파이썬]

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

프로그래머스

 

LRU가 뭔지 일단 알아야 하는 문제. 알고나면 쉽다.

 

배열의 pop(0) 이 아주 시간복잡도를 올리는 녀석으로 알고있는데,

배열의 index 찾아주는 기능을 사용해야 했기 때문에 deque 같은 다른 자료구조 말고 배열을 사용했다.

 

def solution(cacheSize, cities):
    answer = 0
    cachebox = []

    if cacheSize == 0:
        answer = 5 * len(cities)
        return answer

    for city in cities:
        ref = city.lower()
        if ref in cachebox:
            answer += 1
            cachebox.append(cachebox.pop(cachebox.index(ref)))
        else:
            answer += 5
            if len(cachebox) != cacheSize:
                cachebox.append(ref)
            else:
                cachebox.pop(0)
                cachebox.append(ref)

    return answer

# LRU (Least Recently Used) 알고리즘을 활용하는 문제
# 반례가 있었는데 못찾아서 1시간동안 헤맸다.