[프로그래머스] 캐시 / 2018 카카오 블라인드 1차 / 파이썬

Source. 카카오가 신입 개발자 크루를 맞이하는 법

📖 캐시 문제 확인

• 프로그래머스 URL. 캐시 / 2018 카카오 블라인드 1차
• 🎯 정답률: 45.26%

✏️ 문제 해결방법

• 첫 블라인드 공채이기에 속칭 단순 빡구현문제보다 어렵지 않은 문제에 전공 지식을 융합하는 문제가 1번도 그렇고 이번 문제도 그렇고 등장하지 않았나 싶습니다.
• list를 사용해도 되지만 이렇게 반복적인 pop, append가 등장하는 경우 deque를 사용해야 속도에서 이득을 얻습니다.

In python docs I can see that deque is a special collection highly optimized for poping/adding items from left or right sides.

Source. Stack Overflow python: deque vs list performance comparison

• 문제에서 대소문자를 구분하지 않는다고 하였습니다. 이렇게 조건을 빼먹으면 실컷 다 풀고 50점 나옵니다..(ㅎㄷㄷ)
• 문제 풀이의 아이디어는 다음과 같습니다.
  • 리스트에서 도시 하나씩 읽습니다.
  • cache에 읽어온 도시가 있는 경우: [1] 해당 도시를 cache에서 빼서 cache의 맨 좌측으로 이동 [2] time 1 증가
  • cache에 읽어온 도시가 없는 경우
    • 경우1. cache가 꽉찬 경우 [1] cache의 맨 우측의 도시를 제거하여 공간을 확보한 후 읽어온 도시를 cache의 맨 좌측에 둠 [2] time 5 증가
    • 경우2. cache가 빈 경우: [1] 읽어온 도시를 cache의 맨 좌측에 둠 [2] time 5 증가

⭕ 최종 풀이 1

from collections import deque

def solution(cacheSize, cities):
    cache = deque()
    time = 0

    if cacheSize != 0:
        for city in cities:
            city = city.lower()
            if city in cache:
                cache.remove(city)
                cache.appendleft(city)
                time += 1
            elif city not in cache:
                if len(cache) >= cacheSize:
                    cache.pop()
                    cache.appendleft(city)
                    time += 5
                else:
                    cache.appendleft(city)
                    time += 5
    else:
        time += len(cities) * 5

    return time

⭕ 최종 풀이 2

from collections import deque

def solution(cacheSize, cities):
    cache = deque(maxlen=cacheSize)
    time = 0

    for city in cities:
        city = city.lower()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            time += 1
        else:
            cache.append(city)
            time += 5

    return time

• cache = deque(maxlen=cacheSize) 처럼 deque에 최대 길이를 설정해주면 매번 cache의 길이가 넘는지 검사하지 않아도 됩니다.
• 이 경우 deque의 맨 우측이 가장 최근에 검색한 도시입니다.