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

캐시

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

 

입력 형식

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

 

출력 형식

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

 

조건

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

 

---

풀이

 

def solution(cacheSize, cities):
    cache = []
    answer = 0
    if cacheSize == 0 : return len(cities) * 5
    
    for r in cities :
        x = r.lower()
        
        if not x in cache:
            if len(cache) < cacheSize:
                cache.append(x)

            else :
                cache.pop(0)
                cache.append(x)
            answer += 5


        else :
            cache.pop(cache.index(x))
            cache.append(x)
            answer += 1
    
    return answer

 

 

---

풀이 과정

 

캐시 교체 알고리즘 LRU(Least Recently Used)

 

 

cache hit  : 새로운 참조값이 캐시안에 있다면 그 참조값을 가장 최근으로 옮긴다.

 

cache miss : 새로운 참조값이 캐시안에 없다면 가장 오래된 참조값을 없애고 새로운 참조값을 추가한다.

 

 

    참조값               7                 3

 

초기값	cache miss	cache  hit
3	7	3
2	3	7
4	2	2