[프로그래머스] 캐시 (Python)

문제 링크

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

프로그래머스

 

문제 설명

DB 캐시를 적용할 때, 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기와 도시 이름 배열을 입력받는다.
• cacheSize는 정수이며, 범위는 0 <= cacheSize <= 30이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000 개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

 

풀이

LRU 알고리즘 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

cache hit : 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우

cache miss : 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우

 

고려해야할 것

• 캐시 크기 고려
  • 캐시 크기가 0일 때, 저장할수 있는 캐시 공간이 없으므로 모두 cache miss
  • 캐시 크기가 1이상인가?
    • 도시이름이 캐시 안에 존재하는가?
      • 캐시 안에 존재할 경우, 캐시 안의 도시이름을 제거하고, 도시이름을 가장 최근의 페이지에 추가.    (cache hit)
      • 캐시 안에 존재하지 않을 경우(cache miss) , 캐시 공간을 고려하여 도시이름 추가
        • 캐시의 공간이 다 찼을 경우, 가장 오래된 도시이름 제거 후, 도시이름 추가

 

✅ Code - 성공

def solution(cacheSize, cities):
    answer = 0
    
    if cacheSize == 0:
        return 5 * len(cities)
    
    cities = [c.lower() for c in cities]
    cache = []
    for city in cities:   
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
        else:
            if len(cache) == cacheSize:
                cache.pop(0)
            cache.append(city)
            answer += 5
    
    return answer