[Swift] 프로그래머스 - 캐시

문제

https://programmers.co.kr/learn/courses/30/lessons/17680

외부에서 데이터를 긁어오는데 너무 오래걸려서 db에 캐시를 적용하여 성능개선을 시도.

조건

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

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

입력된 도시이름 배열을 순서대로 처리할 때 총 실행시간을 return하는 문제

 

접근방법

LRU 알고리즘이란?

• 가장 최근에 사용되지 않은걸 제거하는 알고리즘. 이 알고리즘의 기본 가설은 가장 오랫동안 사용하지 않았던 데이터는 앞으로도 사용할 확률이 적다는 것.

LRU 예제

• 출처: https://gomguard.tistory.com/115

 

대략적으로 이렇게 생각했어요

loop {
  if cache.count < size {
    if 캐시에 값 없으면 { 넣어줌 }
    else { 업데이트 }
  } else {
    값이 있다면 {
            업데이트
    } 없으면 {
            가장 오래된것에 교체
    }
  }
}

캐시는 push pop이 순서 상관없이 일어날거라 생각해서, 만약 캐시크기가 커지면 shift 하는 시간이 오래걸릴 것 같단 생각에 딕셔너리를 사용했다. 짜다보니 코드가 지져분해졌어요 ㅠ _ㅜ..

 

코드

1. 딕셔너리 풀이

2. 깔끔해보이는 풀이(배열)