(Python) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT) : [1차] 캐시

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

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

 

• 해설 : 

캐시 크기가 주어지고 데이터베이스에 삽입하려는 도시명들이 주어질 때, 이 캐시를 LRU 방식으로 사용하여 삽입한다면 실행시간이 총 얼마나 걸릴지 예상하는 문제이다. 캐시 Hit 일 경우 실행시간은 1, fault일 경우 실행시간은 5이다. 

 

 

 

• 풀이 :

캐시는 queue로 구현하였다. 데이터베이스에 삽입하려는 도시이름들의 순서대로 for문을 실행하고 이 값이 캐시에 있다면 hit로 처리해서 queue의 가장 뒤로 밀어주고 만약 없다면 fault로 처리하여 캐시의 맨 앞, 즉 가장 오래된 요소를 삭제하고 새로이 캐시에 넣어주었다.

 

풀고 나서 드는 생각인데 , heap을 썼다면 remove같은 비효율적인 코드를 실행하지 않고 해결할 수 있었을 것 같다. 나중에 다시 풀어봐야겠다.

 

 

 

from collections import deque
 
def solution(cacheSize, cities):
    cities = [x.lower() for x in cities]
    cache = deque()
    answer = 0
    for i in range(len(cities)):
        if cities[i] in cache:
            cache.remove(cities[i])
            cache.append(cities[i])
            answer += 1
        else:
            cache.append(cities[i])
            if len(cache) > cacheSize:
                cache.popleft()
            answer += 5
            
                   
    return answer