[카카오 코테 2018 | python] 캐시

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17680
• 2018 KAKAO BLIND RECRUITMENT
• level 2

 

Q1) 이 문제는 어떤 문제인가요?
A1) 이 문제는 주어진 도시 이름들을 순차적으로 캐시에 넣으면서, LRU(Least Recently Used) 정책을 적용해 실행 시간을 계산하는 시뮬레이션 문제입니다.

Q2) 이 문제를 어떻게 풀 계획이신가요?
A2) 먼저 도시 이름 리스트를 순회하면서, 도시 이름을 소문자로 통일한 뒤 캐시에 있는지 확인합니다.
캐시에 있으면 cache hit이므로 실행 시간 1을 더하고, 해당 도시를 가장 최근으로 갱신합니다.
캐시에 없으면 cache miss이므로 실행 시간 5를 더하고, 캐시가 가득 찼다면 가장 오래된 항목을 제거한 후 새 도시를 추가합니다.
이 과정을 캐시 사이즈만큼 유지하면서 전체 실행 시간을 누적하고, 마지막에 반환하면 됩니다.

Q3) 캐시 히트/미스는 어떻게 판단하실 건가요?
A3) 캐시 히트 여부는 현재 순회 중인 도시 이름이 캐시 자료구조에 이미 존재하는지 여부로 판단합니다. 도시 이름은 대소문자를 구분하지 않기 때문에, 모두 소문자로 변환한 후 캐시에서 in 연산을 사용해 포함 여부를 확인합니다.

Q4) LRU(Least Recently Used)는 어떻게 구현하실 계획인가요?
A4) LRU는 가장 오래 전에 사용된 항목을 제거하는 캐시 정책입니다.
이를 구현하기 위해 도시가 캐시에 접근될 때마다 해당 도시를 캐시의 가장 뒤로 이동시킵니다.

 

✅ 내 풀이

def solution(cacheSize, cities):
    cache = []
    total_time = 0
    if cacheSize == 0:
        return len([city.lower() for city in cities]) * 5 

    for city in cities:
        city = city.lower()
        if city not in cache:
            if len(cache) >= cacheSize:
                cache = cache[1:]
            cache.append(city)
            total_time += 5
        else:
            cache.remove(city)
            cache.append(city)
            total_time += 1

    return total_time

 

 

---

🤔 OrderedDict 자료구조를 사용해보는게 어때요?

💡최적화된 풀이

from collections import OrderedDict

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

    cache = OrderedDict()
    total_time = 0

    for city in cities:
        city = city.lower()
        
        if city in cache:
            # Cache Hit: 해당 도시를 맨 뒤로 옮기기
            cache.move_to_end(city)
            total_time += 1
        else:
            # Cache Miss
            if len(cache) >= cacheSize:
                # 가장 오래된 항목 제거
                cache.popitem(last=False)
            cache[city] = True
            total_time += 5

    return total_time

✅ 이 코드의 장점

• OrderedDict 덕분에 LRU 정책 구현이 매우 직관적입니다.
• 시간복잡도도 효율적입니다:
  • in, move_to_end, popitem, __setitem__ 모두 평균 O(1) 연산이에요.
• 일반 리스트보다 코드 가독성이 훨씬 좋아지고, 실수 가능성도 줄어듭니다.