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

문제 설명

• 일정 크기(cacheSize)의 배열 내에서 원하는 문자열이 존재하는지 확인 하여 cache hit일 경우 실행시간은 1, cache miss일 경우 실행시간은 5로 전체 실행시간을 구하는 문제
  • caches 배열 내에 존재하지 않을 경우 5를
    1. caches 배열이 cacheSize 보다 작은 경우
    2. caches 배열이 cacheSize 과 같으며 cacheSize 가 0이 아닌 경우
    3. cacheSize가 0인 경우
  • caches 배열 내에 존재할 경우
    1. LRU 알고리즘 수행

겪은 문제

코드_1

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    caches = deque()

    for city in cities:
        if city.lower() not in caches:
            if len(caches) < cacheSize:
                caches.append(city.lower())
            elif len(caches) == cacheSize and cacheSize != 0:
                caches.popleft()
                caches.append(city.lower())
            elif cacheSize == 0:
                continue
            answer += 5
        else:
            answer += 1

    return answer

• 위와 같이 구현했을때 cacheSize 가 0 으로 주어진 테스트 케이스에서 answer이 더해지지 않는 것을 확인하였고 continue와 pass를 헷갈려 겪은 문제, 코드_2에서 수정
  • continue : 바로 다음 순번의 loop 수행
  • pass : 다음 행동을 진행

코드_2

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    caches = deque()

    for city in cities:
        if city.lower() not in caches:
            if len(caches) < cacheSize:
                caches.append(city.lower())
            elif len(caches) == cacheSize and cacheSize != 0:
                caches.popleft()
                caches.append(city.lower())
            elif cacheSize == 0:
                pass
            answer += 5
        else:
            answer += 1

    return answer

• 현재 city가 caches내에 존재하는 경우 answer에 1을 더하는 것 외에 LRU 알고리즘을 수행하지 않는 다는 것을 발견함 (LRU가 뭔지 몰랐음)
• LRU 알고리즘 수행을 위해 현재 city가 caches에 존재 하는 경우 caches에서 city의 위치를 마지막으로 변경시키게 구현

코드는 여기서

• 그래도 친절한 문제다 lower()로 바꿔야 하는 부분이나 조건문 케이스 나누는 부분에서 있을 수 있는 실수는 테스트 케이스에서 걸리게 해줌
• LRU 알고리즘이라는 배경지식이 없으면 먼저 알아보고 풀어야 하는 문제