[프로그래머스 Lv2,python]- [1차]캐시

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

프로그래머스

def solution(cacheSize, cities):
    answer = 0
    cache=[]
    for a in range(len(cities)): # 대소문자 상관없도록 소문자로 통일해줌
        cities[a]=cities[a].lower()
    for a in cities:
        if a in cache: # 캐시에 존재하면 그 데이터를 지우고 뒤에 추가해준다.
            cache.remove(a)
            cache.append(a)
            answer+=1
        else: # 존재하지 않으면
            if(len(cache)==cacheSize and cacheSize>0): # 캐시 길이가 최대이거나 사이즈가0보다 크면 맨앞 삭제
                cache.pop(0)
            if (cacheSize>0): # 그리고 추가하기
                cache.append(a)
            answer+=5
    return answer

LRU 알고리즘을 사용하였다.

 

> LRU 알고리즘이란?

페이지 교체 알고리즘의 종류로 페이지의 부재가 발생했을 때, 가장 오랫동안 사용되지 않은 페이지를 제거한다. 만약 같은 데이터가 있다면 원래 있는 데이터를 삭제하고 뒤에 추가해준다.

Cache hit는 요청된 데이터가 이미 캐시에 존재하는 경우이다.

Cache miss는 요청된 데이터가 캐시에 존재하지 않는 경우이다.

 

만약 캐시의 크기가 3이고, 데이터가 [1,3,4,3,5,1]이라면?

캐시에는 [1,3,4]가 저장되고 난뒤 다음 데이터가 3인데 이미 캐시에 존재하므로 원래 있는 3을 삭제하고 4를 앞으로 보낸뒤 맨 뒤에 3을 추가하여 [1,4,3]이 된다. 그다음은 5인데 캐시에 존재하지 않으므로 가장 오랫동안 사용되지 않은 데이터인 1을 삭제하고 맨뒤에 추가해주어 [4,3,5]가 된다. 그 다음 1도 존재하지 않으므로 [3,5,1]이 된다.