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

문제

https://programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

코딩테스트 연습 - [1차] 캐시

 

코드

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

cacheSize가 주어지고 cache안에 있는 도시이름을 사용할 때는 1이 들고 cache에 없을 경우에는 5에 시간이 든다.

만약 cacheSize가 0일 경우는 무조건 5에 시간이 들기 때문에 5 * len(cities)를 리턴해준다.

 

대문자 소문자를 구별 안해주므로 모두 같게 소문자로 만들어서 비교한다.

stack에 i가 존재한지 확인 후 존재한다면 stack에 존재하는 i를 제거하고 새로 append를 시켜준다.

 

stack에 i가 존재하지 않을 경우에는 stack에 append를 시키는데 만약 stack이 꽉찻다면 pop(0)을 해줘 가장 먼저 들어온 값을 빼준다. 

왜냐하면 캐시교체 알고리즘은 LRU를 사용하기 때문에 가장 오래된 값을 빼준다.

(LRU는 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법)