[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. 딕셔너리 풀이

	func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
	if cacheSize == 0 { return cities.count*5 }
	var cache: [String:Int] = [:]
	var cacheForKey: [Int:String] = [:]
	var idxList: Set<Int> = []
	var rst = 0
	var idx = 0
	let update: (Int, String) -> () = { index, ipt in
	cache[ipt] = idx
	cacheForKey[idx] = ipt
	idxList.remove(index)
	idxList.insert(idx)
	idx += 1
	rst += 1
	}
	let insert: (String) -> () = { ipt in
	cache[ipt] = idx
	cacheForKey[idx] = ipt
	idxList.insert(idx)
	idx += 1
	rst += 5
	}
	let newData: (Int, String, String) -> () = { min, key, ipt in
	cache.removeValue(forKey: key)
	cache[ipt] = idx // 갱신
	cacheForKey.removeValue(forKey: min)
	cacheForKey[idx] = ipt
	idxList.remove(min)
	idxList.insert(idx)
	idx += 1
	rst += 5
	}
	cities.forEach {
	let ipt = $0.lowercased()
	if cache.count < cacheSize {
	if let index = cache[ipt] {
	update(index, ipt)
	} else {
	insert(ipt)
	}
	} else {
	// 값이 있다면
	if let index = cache[ipt] {
	update(index, ipt)
	} else {
	// 가장 오래된 것 삭제
	if let min = idxList.min(), let key = cacheForKey[min] {
	newData(min, key, ipt)
	}
	}
	}
	}
	return rst
	}

view raw 캐시.swift hosted with ❤ by GitHub

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

	// 깔끔해보이는 코드.. 속도는 딕셔너리가 더 빨랐다.
	func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
	if cacheSize == 0 { return cities.count*5 }
	var rst = 0
	var cache: [String] = []
	let LRU: (String) -> () = { ipt in
	if cache.contains(ipt) { cache.remove(at: cache.firstIndex(of: ipt)!)}
	if cache.count == cacheSize { cache.removeLast() }
	cache.insert(ipt, at: 0)
	}
	cities.forEach {
	let ipt = $0.lowercased()
	if cache.contains(ipt) { rst += 1}
	else { rst += 5}
	LRU(ipt)
	}
	return rst
	}

view raw 캐시2.swift hosted with ❤ by GitHub