[프로그래머스][level2] [1차] 캐시

문제 링크

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

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

풀이 

- deque 사용해서 풀이 

- 큐가 캐시 역할 

- LRU(Least Recently Used) : 가장 오래전에 사용된 거 삭제 

 

1. 캐시 사이즈가 0일 경우 모두 cache miss이므로 실행 시간 5 * 처리할 도시 개수리턴 

 

2. 배열에 들어있는 도시들 순서대로 

대소문자 구분 없으므로 모두 소문자로 변경 

- 큐에 도시가 들어있다면, cache hit 이므로 answer + 1, 실행 순서 변경을 위해 큐에서 삭제 후 다시 큐에 삽입,

- 큐에 도시가 없다면, answer + 5 

   큐에 캐시 사이즈만큼 도시가 들어가 있다면 하나 삭제 후 다시 캐시에 넣어야 하므로 popleft 후 도시 삽입 

   큐에 도시가 들어갈 수 있다면 도시 삽입 

from collections import deque

def solution(cacheSize, cities):
    answer = 0
        
    # 캐시 사이즈가 0일 때 
    if cacheSize == 0:
        return 5 * len(cities)
    
    q = deque()
    for i in cities:
    	# 모두 소문자로 변경 
        i = i.lower()
        # 큐에 존재한다면 
        if i in q :
        	# 삭제 후 다시 삽입 
            q.remove(i)
            q.append(i)
            # 실행 시간 + 1 
            answer += 1 
        # 큐에 존재하지 않는다면 
        else:
        	# 큐에 캐시 사이즈만큼 도시가 들어가 있다면 
            if len(q) == cacheSize :
            	# 가장 오래전에 삽입된 거 삭제 후 도시 삽입 
                q.popleft()
                q.append(i)
            # 큐에 도시가 더 들어갈 수 있다면 
            else:
                q.append(i)
            # 실행 시간 + 5 
            answer += 5
            
    return answer