문제 보기 · Level 2 · 2018 KAKAO BLIND RECRUITMENT (1차) · 정답률 67% · 푼 사람 25,932명 (2026-09-30 기준)1

문제

도시 이름 배열을 순서대로 조회한다. 캐시 크기는 cacheSize이고, 교체 방식은 가장 오래 쓰지 않은 것부터 버리는 LRU다. 캐시에 있으면(hit) 1, 없으면(miss) 5가 걸린다. 총 실행 시간을 돌려준다. 도시 이름은 대소문자를 구분하지 않는다.

  • 0 ≤ cacheSize ≤ 30
  • 도시 최대 100,000개, 이름 최대 20자

풀이

막히면 한 단계씩 펼친다.

필요한 개념

큐와 덱의 “가장 오래 안 쓴 것 버리기(LRU)”: 캐시를 쓴 순서대로 줄 세운 덱으로 만든다.

1단계 · 작은 예로 손으로 풀기

캐시 크기 2, 도시 [a, b, a, c, b] (왼쪽이 가장 오래 안 쓴 것)

도시 캐시에 있나 시간 캐시
a 없음 +5 [a]
b 없음 +5 [a, b]
a 있음 +1, a를 맨 뒤로 [b, a]
c 없음, 가득 참 +5, 맨 앞 b를 버림 [a, c]
b 없음, 가득 참 +5, 맨 앞 a를 버림 [c, b]

총 21이다. 세 번째에 a를 맨 뒤로 옮기지 않았다면 c가 올 때 a가 버려졌을 것이다.

2단계 · 가장 단순한 방법과 그 속도

도시마다 캐시(최대 30개)를 훑어 있는지 본다. 10만 × 30 = 300만 번이라 넉넉하다. 캐시가 작아서 덱의 in과 remove가 \(O(30)\)이어도 괜찮다.

3단계 · 핵심 아이디어

덱을 “쓴 순서”로 유지한다. 맨 앞이 가장 오래 안 쓴 것이다.

  • hit: 덱에서 빼서 맨 뒤에 다시 넣는다. 방금 썼기 때문이다.
  • miss: 가득 찼으면 맨 앞을 버리고, 새 도시를 맨 뒤에 넣는다.

두 가지를 더 챙긴다. 이름은 소문자로 바꿔 비교한다. 캐시 크기가 0이면 아무것도 넣지 않고 모두 miss다.

4단계 · 코드 흐름
  1. 빈 덱과 시간 0을 준비한다.
  2. 도시마다 소문자로 바꾼다.
  3. 덱에 있으면: 빼서 맨 뒤에 넣고 +1.
  4. 없으면: +5. 크기 0이면 넘어간다. 가득 찼으면 맨 앞을 빼고, 도시를 맨 뒤에 넣는다.
  5. 시간을 돌려준다.
5단계 · 파이썬 코드 
from collections import deque

def solution(cacheSize, cities):
    cache = deque()
    time = 0
    for city in cities:
        city = city.lower()
        if city in cache:                 # hit
            cache.remove(city)
            cache.append(city)            # 방금 쓴 것으로
            time += 1
        else:                             # miss
            time += 5
            if cacheSize == 0:
                continue
            if len(cache) == cacheSize:
                cache.popleft()           # 가장 오래 안 쓴 것 버리기
            cache.append(city)
    return time
  • continue: 이번 도시의 남은 줄을 건너뛰고 다음 도시로 간다.
  • cache.remove(city): 덱 안에서 그 값을 찾아 지운다.

deque(maxlen=cacheSize)를 쓰면 더 짧다. 가득 찬 덱에 append하면 맨 앞이 저절로 빠지고, maxlen=0이면 아무것도 들어가지 않는다.

def solution(cacheSize, cities):
    cache = deque(maxlen=cacheSize)
    time = 0
    for city in map(str.lower, cities):
        if city in cache:
            cache.remove(city)
            time += 1
        else:
            time += 5
        cache.append(city)
    return time
6단계 · 실행 추적

캐시 크기 3, 도시 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul]

  • 처음 세 개는 miss: 5 × 3 = 15, 캐시 [jeju, pangyo, seoul]
  • 나머지 여섯 개는 모두 캐시에 있다: hit 6번 = 6

총 21이다. hit마다 맨 뒤로 옮겨도 세 도시가 모두 캐시에 남는다.

7단계 · 복잡도와 흔한 실수

도시 N개마다 캐시 K칸을 훑으니 \(O(NK)\)다(K ≤ 30).

  • 대소문자를 구분해서 NewYork과 newyork을 다른 도시로 본다.
  • hit일 때 맨 뒤로 옮기지 않는다. 그러면 LRU가 아니라 “먼저 넣은 것부터 버리기(FIFO)”가 된다.
  • 캐시 크기 0을 따로 처리하지 않아, 빈 덱에서 popleft를 하다 오류가 난다.
검증: 문제의 예시 6개를 통과했고, 무작위 입력 3,000개에서 OrderedDict로 만든 LRU 풀이와 maxlen 풀이가 모두 같은 결과를 냈다 — 11_pg17680_p1.py

  1. 프로그래머스 스쿨, “[1차] 캐시” (https://school.programmers.co.kr/learn/courses/30/lessons/17680), 2026-09-30 조회. ↩