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

사용 언어: Python3

문제

괄호의 값

풀이

나의 풀이

from collections import deque
def solution(cacheSize, cities):
    
    if cacheSize <= 0: # ✅ 예외상황 처리하지 않으면 일부 테스트 케이스를 통과할 수 없다 !!
        return len(cities) * 5
    
    ans = 0
    cache = deque()
    for city in cities:
        city = city.lower() # 도시 이름 소문자 통일
        if city in cache:
            ans += 1
            cache.remove(city)
        else:
            ans += 5
            if cache and len(cache) >= cacheSize: # 캐시가 비어있지 않으면서 cacheSize보다 크면
                cache.popleft() # 제일 나중에 들어온 도시를 pop
        cache.append(city)
    return ans

• 테스트 케이스: 통과
• 제출 결과: 통과
  
• 캐시 교체 알고리즘에 LRU 알고리즘을 사용한다고 했을 때 LRU가 정확히 기억나지는 않았지만,
  괄호로 주어진 Least Recently Used을 보고 가장 최근에 사용된 것으로 캐시를 교체하는 방식이라고 생각했다.
• deque 자료구조를 두고 주어진 값(도시)가 캐시 안에 있는 경우(=cache hit)와 없는 경우(=cache miss)로 나눠서 처리했다.
  • deque의 길이가 cacheSize와 같거나 넘은 경우에는 popleft()로 가장 왼쪽(오래전 들어온) 요소를 pop 했다.
• cacheSize가 0 인 경우 예외상황을 처리해주어야 하는데, 이걸 발견하기까지 시간이 약간 걸렸다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기