[프로그래머스] 캐시 - python

캐시

문제

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

제한사항

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

조건

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

풀이

q = 현재 캐시 상태

now = 현재 캐시에 들어 있는 도시 표시

LRU는 가장 오랫동안 사용하지 않은 캐시를 교체하는 알고리즘이므로 교체되지 않을 때까지 매번 1씩 시간을 카운트해준다.

• 캐시에 빈 공간이 있을 경우 바로 넣는다.
• 빈 공간이 없을 경우
  • page fault일 때: 내림차순으로 정렬해서 가장 오랫동안 사용되지 않은 캐시 자리에 현재 값을 넣어 준다.
  • 캐시 hit일 경우 : 사용된 캐시를 찾아서 시간을 0으로 초기화 해준다.

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    if cacheSize == 0:
        return 5 * len(cities)
    
    cities = [city.upper() for city in cities]
    
    q = []
    now = []
    for i, city in enumerate(cities):
        q = [(i + 1, city) for i, city in q]
        if city not in now:
            if len(q) < cacheSize: # 초기 
                q.append((0, city))
                now.append(city)
                answer += 5
            else:# page fault일 때
                q.sort(key=lambda x:(-x[0], x[1]))
                answer += 5
                _, c = q[0]
                now[now.index(c)] = city
                q[0] = (0, city)
​
        else:
            for j , v in enumerate(q):
                cnt, c = v
                if city == c:
                    q[j] = (0, c)
            answer += 1
    return answer

오로지 정확성을 위한 풀이 ..

다른 사람 풀이

deque의 maxlen을 사용하면 바로 배열 사이즈를 정할 수 있다. maxlen 이상의 값을 추가할 경우 append()을 하게 되면 맨 왼쪽 원소가 삭제되고 appendleft()를 할 경우 맨 오른쪽의 원소가 삭제되고 값이 추가된다.

cache hit 일 때: 해당 값을 꺼내고 다시 넣는다.

cache miss일 때: 해당 값을 넣는다. 자동으로 맨 왼쪽 원소(가장 처음에 들어간 원소)가 삭제된다.

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    cache = deque(maxlen=cacheSize)
    
    for c in cities:
        city = c.upper()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
        else:
            cache.append(city)
            answer += 5
            
    return answer