[level2] Cache

✏️문제 설명

---

✏️문제풀이

페이지(캐시) 교체 알고리즘 (LRU)

• 사용자에게 빠르게 정보를 제공하기 위해 사용하는 캐시에서 새로운 데이터가 발생했을 때, 가장 오래전에 사용된 데이터를 제거하고 새로운 데이터를 삽입하는 알고리즘

1. 새로운 데이터가 들어온 경우
① 캐시에 넣어준다.
② 캐시가 가득 차있다면, 가장 오래된 데이터를 제거하고 넣어준다.

2. 캐시에 존재하는 데이터가 들어온 경우
① 해당 데이터를 꺼낸 뒤,
② 가장 최근 데이터 위치로 보내준다.

---

💡CODE

def solution(cacheSize, cities):
    cache = []
    time = 0
    for city in cities:
        city = city.lower()
        if cacheSize:
            if not city in cache:
                if len(cache) == cacheSize:
                    cache.pop(0)
                cache.append(city)
                time += 5
            else:
                cache.pop(cache.index(city))
                cache.append(city)
                time += 1
        else:
            time += 5
    return time

• cache라는 빈 배열을 만든다.
• .lower(): city는 대소문자를 구별하지 않으므로 for문을 돌며 cache 배열에 접근할 때 모두 소문자로 변경하여 저장한다.
• cacheSize가 0인 경우에는 cache에 저장이 불가능 하므로 cache miss만 발생하여 매번 실행 시간이 5초가 되어 time에 5를 계속 더해준다.
• cacheSize가 1 이상인 경우, cache hit인지 cache miss인지 판별을 해야 하므로 cache에 city가 존재하는지 확인해야 한다.
• cache miss인 경우, 먼저 cacheSize와 cache의 길이가 같은 지 확인한다. 만약 같다면 더 이상 cache에 저장할 용량이 없다는 뜻으로 cache.pop(0)으로 cache의 첫 번째 값을 제거한다. 이후, cache에 cache.append(city)로 city를 저장한다. 실행 시간은 5초이므로 time에 5를 더한다.
• cache hit인 경우, 이전에 같은 이름의 city가 존재하므로 이는 가장 최근에 참조 되었다는 의미가 되므로 cache에 있던 city를 삭제한 뒤, 맨 뒤에 city를 다시 저장한다. 실행 시간은 1초이므로 time에 1을 더한다.