[1차] 캐시

캐시(페이지) 교체 알고리즘 : LRU(Least Recently User) 문제이다.

1. 캐시 Miss!

• 데이터가 들어왔을 때, 그 데이터가 캐시에 없다면, 캐시 Miss!이다.
• 이 경우, 가장 오래 전에 사용된 데이터를 제거하고 새로 들어온 데이터를 삽입한다.

2. 캐시 Hit!

• 데이터가 들어왔을 때, 그 데이터가 캐시에 있다면, 캐시 Hit!이다.
• 이 경우, 해당 데이터를 꺼내 캐시의 맨 뒤에 넣어준다.
• = 가장 최근에 쓰였을 수록 맨 뒤에 있다.
• = 가장 나중에 쓰였을수록 맨 앞에 있다.

queue를 이용

def solution(cacheSize, cities):
    cache = []
    running_time = 0
    cities = list(map(lambda city: city.lower(), cities))
    for ref in cities:
        if cacheSize == 0: # cacheSize가 0인 경우 예외 처리
            return len(cities)*5
        if not ref in cache:
            if len(cache) < cacheSize:
                cache.append(ref)
            else:
                cache.pop(0)
                cache.append(ref)
            running_time += 5

        else:
            cache.pop(cache.index(ref))
            cache.append(ref)
            running_time += 1

    return running_time

주의

• cacheSize가 0인 경우 예외 처리

  • if cacheSize == 0인 경우, 모든 경우 Miss!가 난다.

• cities의 이름이 대소문자가 섞여나오는데 구분하지 않음

  • list(map(lambda city: city.lower(), cities)) 이용하여 모든 문자를 대문자 혹은 소문자로 변경한다.