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

프로그래머스

 

문제

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

프로그래머스

 

 

풀이

처음에 문제를 읽고 조금 당황했었는데 LRU(Least Recently Used) 알고리즘을 이용하여 문제를 풀이하라고 했기 때문이다. 그래서 혹시 이런 알고리즘 류를 외워서 풀어야 하는가 했으나, 커뮤니티에 의하면 해당 테스트 쳤을 당시에 검색을 통해 알고리즘 참고하여 문제를 했다고 적혀 있길래 나도 LRU 알고리즘을 검색하여 이해한 후 문제를 풀이하였다. 

 

https://j2wooooo.tistory.com/121

LRU 알고리즘은 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법으로 리스트를 하나 생성해 둔 뒤, 페이지를 적재하는 형식으로 시작한다. 적재하는 페이지가 리스트 안에 있다면 해당 인덱스에 있던 값을 리스트의 맨 뒤로 보낸다. 만약 리스트가 꽉 찬 상태에서 리스트 안에 없는 페이지가 들어온다면 리스트의 맨 앞에 있는 페이지를 삭제하고 새로운 페이지를 리스트 맨 뒤에 넣는 방식으로 진행된다. 

 

이를 이용하여 파이썬 풀이를 작성하면 다음과 같다. 

 

 

🖥️ main.py

def solution(cacheSize, cities):
    
    cities = list(map(lambda x: x.lower(), cities))
    
    total_time = 0
    cities_list = []
    
    for i in cities:
        if i in cities_list:
            value = cities_list.pop(cities_list.index(i))
            cities_list.append(value)
            total_time += 1
    
        elif len(cities_list) < cacheSize:
            cities_list.append(i)
            total_time += 5
            
        elif len(cities_list) >= cacheSize:
            cities_list.append(i)
            cities_list.pop(0)
            total_time += 5
    
    return total_time

 

처음에 리스트 앞, 뒤 요소만 pop, append 하는 형식으로 알고리즘이 진행될까 봐 deque()을 도입할까 고민했었지만 코드를 작성하는 도중에 리스트 안에 페이지가 있다면 그 페이지가 있는 값을 빼서 뒤로 보내줘야 하므로 deque() 사용이 부적절하다고 판단 들어 list로 진행하여 문제를 풀었다. 

 

 

---

참조 : https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)