🐳2018 KAKAO BLIND RECRUITMENT [1차] 캐시 ⭐⭐ 코딩 테스트 문제를 풀고 정리한 글입니다 🐳

💫 문제 설명

매개변수

• cacheSize: 캐시 크기
  • 정수
  • 0 ≦ cacheSize ≦ 30
• cities: 도시 이름 문자열 배열
  • 최대 도시 수 100,000개
  • 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성
    • 대소문자 구분 X
    • 도시 이름은 최대 20자

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

→ 입력된 도시이름 배열을 순서대로 처리할 때, 총 실행시간을 출력

💫 코드

def solution(cacheSize, cities):
    cities = [citi.upper() for citi in cities]
    arr = []
    time = 0

    if cacheSize == 0:
        return len(cities) * 5
    else:
        for citi in cities:
            if citi in arr:
                arr.pop(arr.index(citi))
                arr.append(citi)
                time += 1
            else:
                if len(arr) >= cacheSize:
                    arr.pop(0)
                arr.append(citi)
                time += 5

    return time

💫 Least Recently Used (LRU)란?

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 데이터를 우선적으로 제거하는 캐싱 알고리즘이다.

→ 최근에 자주 접근된 데이터는 캐시에 남기고, 오래 방치된 데이터부터 제거하여 캐시 공간을 효율적으로 사용