[프로그래머스 2018 KAKAO BLIND RECRUITMENT] [1차] 캐시(Lv.1) - 파이썬(Python)

문제

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

프로그래머스

 

풀이

1. deque 사용

from collections import deque

 

• deque는 양방향에서 빠른 삽입과 삭제를 지원하는 자료구조입니다. 캐시에서 데이터를 추가하고 삭제할 때 빠른 처리를 위해 사용됩니다.

2. 캐시 크기 예외 처리

if cacheSize == 0:
    return len(cities) * 5

• 캐시 크기가 0일 때는 캐시가 작동하지 않으며, 모든 도시에서 무조건 캐시 미스가 발생합니다. 따라서 도시의 개수만큼 5를 곱해 미스 시간의 총합을 반환합니다.
• 캐시가 없다는 상황을 미리 처리하여 나머지 코드를 간결하게 유지하고, 실행 시간을 절약합니다.

3. 캐시 및 도시 이름의 대소문자 통일 처리

cache = deque(maxlen=cacheSize)  # 캐시 크기 설정

• deque에 maxlen을 설정하여 캐시가 최대 크기를 넘기면 자동으로 가장 오래된 항목을 제거하게 만듭니다. 캐시의 크기를 명시적으로 관리하지 않고 deque가 알아서 처리해줍니다.

for city in cities:
    city = city.lower()

• 도시 일므의 대소문자를 구분하지 않기 위해 lower() 함수를 사용해 모든 도시 이름을 소문자로 변환합니다.

4. 캐시 히트 및 미스 처리

if city in cache:
    answer += 1  # 캐시 히트
    cache.remove(city)  # 기존 위치에서 제거 후 최신화
else:
    answer += 5  # 캐시 미스

• 캐시 히트 처리
  • 도시가 캐시에 이미 존재하는 경우 캐시 히트로 간주됩니다. 이때 실행 시간을 1만 추가합니다. 또한 캐시의 기존 위치에서 해당 도시를 제거하고 최신 항목으로 다시 추가해야 하므로 cache.remove(city)를 실행합니다.
• 캐시 미스 처리
  • 도시가 캐시에 없으면 캐시 미스로 간주되며, 실행시간을 5 추가합니다. 이때는 돌의 remove 없이 바로 캐시에 도시를 추가합니다.

4. 캐시 관리

cache.append(city)

• 도시가 캐시에 없거나, 캐시 히트로 인해 제거된 후 다시 캐시의 맨 뒤에 추가합니다. 이때, deque의 maxlen이 설정되어 있기 때문에, 캐시가 가득 찼다면 자동으로 가장 오래된 항목이 삭제됩니다.
• deque가 자동으로 항목을 관리함으로써 캐시 크기 제한을 초과할 때 발생하는 문제를 간단하게 해결합니다.

 

최종코드

from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return len(cities) * 5  # 캐시 크기가 0일 때는 무조건 캐시 미스

    answer = 0
    cache = deque(maxlen=cacheSize)  # deque에 maxlen을 설정하여 자동으로 관리

    for city in cities:
        city = city.lower()  # 대소문자 구분 없애기

        if city in cache:
            answer += 1  # 캐시 히트
            cache.remove(city)  # 기존 위치에서 제거 후
        else:
            answer += 5  # 캐시 미스
        
        cache.append(city)  # 캐시의 끝에 추가 (자동으로 오래된 항목 제거)

    return answer