[programmers] 1차 캐시

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

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

 

문제 이해

캐시 크기가 3, 도시이름이 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] , 실행시간이 50일때

 

처음에는 크기가 3인 빈 캐시가 있다.

1. 주어진 도시 순서대로 jeju, pangyo, seoul이 순서대로 들어가고, cache에 각 도시들에 대한 정보가 없기 때문에 cache miss 조건으로 실행시간은 +5씩 해서 15가 된다.

 

seoul까지는 캐시 공간이 비어서 쉽게 들어갔지만, 이제 캐시 공간이 다 찼다.

2. 다음 도시인 newyork가 들어갈 때는 cache에 newyork이 없으므로 저장된 도시 중 하나를 빼야한다. 

-> 문제의 조건에 따라 Least Recently Used 순서대로 없앤다. 즉, 가장 처음에 들어온 도시인 Seoul을 제거하고 newyork를 맨 마지막에 삽입한다.

-> 이렇게 해서 가장 최근에 저장한 도시는 new york이 되고, 저장한지 가장 오래된 도시는 pangyo가 된다. 

-> newyork은 miss cache이므로 실행시간 +5 되어 총 20만큼 실행됐다. 

 

3. 그 다음 도시인 'LA'를 cache에 삽입할 때 역시 cache공간이 부족하므로 가장 오래된 pangyo를 빼고 맨 마지막에 LA를 삽입해야한다. 

 

위와 같은 과정을 반복하여 실행시간을 구하는 것이 문제의 목표이다.

 

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    cache = deque([])
    if cacheSize == 0:       #cacheSize가 0이라면 모든 도시 정보를 불러오는데 5*len(cities)만큼 걸린다.
        return len(cities)*5 
    
    for city in cities:   
        city = city.lower()  #대소문자 구분 없앤다는 조건
        
        if city in cache:    # cache 안에 도시 정보가 있다면   
            answer+=1        # cache hit으로 실행시간 +1
            cache.remove(city)
            cache.append(city)   # 가장 최근에 저장한 도시로 update을 위해 remove하고 다시 append
        else:
            answer+=5
            if len(cache) >= cacheSize:    # 캐시 공간을 다 썼다면 LRU로 맨 처음에 들어간 도시를 꺼낸다
                cache.popleft()
                cache.append(city)
            else:
                cache.append(city)
    
            
    return answer