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

---

1. 전체 코드

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    q = deque(cities)
    cache = deque()
    while q:
        locale = q.popleft().lower()
        # case1
        if locale in cache:
            for i in range(len(cache)):
                if cache[i] == locale:
                    find = i
                    break
            temp = cache[i]
            del cache[i]
            cache.append(temp)
            answer += 1
        # case2
        else:
            cache.append(locale)
            answer += 5
        if len(cache) > cacheSize:
            cache.popleft()
    return answer

s = 3
c = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]
print(solution(s, c))

---

2. 풀이

LRU(Least Recently Used)는 가장 오랬동안 사용되지 않은 캐시를 삭제하는 알고리즘이다. 캐시 내부에 동일한 값은 존재하지 않는다.

알고리즘:
리스트의 왼쪽으로 갈수록 오랬동안 사용하지 않은 캐시이다. 따라서 새로 들어온 캐시는 항상 마지막 항에 위치한다.

---

case1: locale이 cache에 이미 존재하는 경우

1. cache = [제주, 판교, 서울] <- 판교(locale)
2. 판교의 index = 1, del cache[1]
3. cache = [제주, 서울], cache.append('판교')
4. cache = [제주, 서울, 판교]

---

case2: locale이 cache에 존재하지 않는 경우

1. 그냥 cache.append('판교') 해준다.
2. cache = [제주, 뉴욕, 서울, 판교]

---

마지막으로는, cache의 길이가cacheSize를 초과할 수 있으므로 조건문을 통해 확인한다. 만약 초과했다면, 가장 오래된 locale을 제거하기 위해 popleft()를 통해 첫 번째 원소를 제거한다.