[프로그래머스] 캐시

프로그래머스

 

한줄 정리 : 조건부 스택

 

이문제를 풀기 위해서는 먼저 LRU알고리즘을 알아야 한다.

LRU알고리즘이란 페이지 교체 알고리즘이라고 하는데

페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. 이 알고리즘이 사용되는 시기는 페이지 부재가 발생해 새로운 페이지를 적재 해야하나 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용된다.

 

페이지 교체 알고리즘의 종류로 페이지 부재가 발생했을 경우 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다. 이 알고리즘은 가장 오래동안 사용되지 않은 페이지는 앞으로도 사용할 확률이 적다는 가정 하에 사용한다.

맨 왼쪽 흰색 배경이 초기의 캐시이고 밑으로 갈 수록 오래 된 페이지라고 가정한다.

위와 같이 참조하는 값이 캐시안에 없으면 가장 오래 전에 참조한 값을 빼고 현재 값을 캐시에 넣어준다.

반대로 참조하는 값이 캐시안에 있으면 해당 값을 캐시의 가장 최근 위치에 넣어준다.

 

1. 우선 캐시 사이즈가 0일 경우, 모든 cities가 miss -> 따라서 return len(cities) * 5
2. city이름 대소문자 구분 없으므로 대문자로 통일: city.upper() 사용
3. 만약 city가 캐시 메모리에 있을 경우:
   • 지금의 city가 가장 최근에 사용된 것이므로 맨 마지막에 빠지도록 위치 변경
   • cache hit -> answer += 1 
4. 만약 city가 캐시 메모리에 없을 경우
   • 만약 캐시에 빈 공간이 있을 경우:
     • 캐시에 city 보관.
   • 캐시에 빈 공간이 없을 경우:
     • 캐시에서 사용된지 오래된 city를 빼고, 현재 city를 캐시에 보관

def solution(cacheSize, cities):
    answer = 0
    i = 0              # 초기 캐시 인덱스
    cache = []
    if cacheSize == 0:                # 캐시 사이즈가 0이면,
        return len(cities)*5		  # cache miss이므로 *5
    for c in cities:              
        city = c.upper()              # city 이름 대문자 통일
        if city in cache:             # 캐시에 이미 있는 city의 경우
            cache.remove(city)        # 해당 city 캐시에서 위치 재조정
            cache.append(city)
            answer += 1
        else:                         # 캐시에 없는 city의 경우
            answer += 5 			  # cache miss이므로 *5
            if i < cacheSize:         # 아직 캐시에 빈 공간이 있다면
                cache.append(city)
                i += 1
            else:                     # 캐시에 빈 공간이 없다면
                cache.pop(0)          # 캐시 내부 city 하나 교체
                cache.append(city)

    return answer