[프로그래머스] Level 2_[1차]캐시(2018 KAKAO BLIND RECRUITMENT)

📌문제 유형

2018 KAKAO BLIND RECRUITMENT

 

📌문제

프로그래머스

 - LRU 알고리즘이란?

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

 

📌나의 문제풀이

 - cities : city는 대소문자 구분하지 않아 lower로 통일

 - cachesize == 0일때는 크기만큼 리턴

 - cacheSize보다 작을 때, 같을 때 고려하기

def solution(cacheSize, cities):
    answer = 0
    cities = [city.lower() for city in cities]
    visit = []
    
    if cacheSize == 0:
        return 5 * len(cities)
    
    for city in cities:
    	# cacheSize보다 작을 때
        if len(visit) < cacheSize:
            if city not in visit:
                visit.append(city)
                answer += 5
            else:
                visit.remove(city)		# visit에 있으면 삭제 후
                visit.append(city)		# 뒤에 다시 넣기
                answer += 1
        # cacheSize랑 같을 때
        else:
            if city not in visit:
                visit.append(city)
                answer += 5
                visit.pop(0)		# cacheSize 맞추기위해 삭제
            else:
                visit.remove(city)
                visit.append(city)
                answer += 1
            
    return answer

 

📌다른 사람들의 문제풀이

1) deque의 maxlen 사용

 - maxlen

[Python] deque 기본 설정( deque(iterable, maxlen) )

import collections

def solution(cacheSize, cities):    
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
            
    return time

 

📌리뷰

 - deque의 maxlen으로 리스트 크기 조절 가능

 - LRU 알고리즘