[Swift] 프로그래머스 [1차] 캐시(lv. 2)

[Swift] 프로그래머스 [1차] 캐시(lv. 2)

 

1. 문제

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

프로그래머스

 

2. 접근

캐시 교체 알고리즘은 모르기 때문에 따로 구글링을 해서 찾아보았다.

https://dailylifeofdeveloper.tistory.com/355

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

 

이것을 참조했는데, LRU 알고리즘을 쉽게 이야기하면, 안 나온 것은 안 나올 확률이 높고, 나온 것은 또 나올 확률이 높다는 것에서 포인트를 얻은 알고리즘이라고 생각하면 된다.

 

예를 들어 어떤 시험의 기출분석을 하는데 최근 3개년 기출은 나올 가능성이 높지 않은가?

그래서 나의 노트(캐시)에 들어있으면 접근이 빠르다. 하지만, 15년 전 기출은? 그런데 15년 전 기출이 중요해도 안 나온 지 15년이 되었다면...?

계속 노트에 가지고 있으면 낭비가 아니겠나. 그래서 과감히 삭제해주고 최신 기출들을 담아 놓는 것이다.

 

캐시 사이즈가 얼마인지에 따라, 그리고 등장한 값이 무엇인지에 따라 스택에 무엇인가를 쌓고, 없애주면 되는 것이다.

아래에서는 stack 안에 도시 이름이 있으면 그 스택에 존재하는 값을 제거하고 다시 위에 그 도시 이름을 쌓아주고, stack 안에 도시 이름이 없으면, stack에 계속 쌓아주는 로직을 구현했다.

 

LRU 알고리즘... 빠른 시일 내에 한 번 깊게 공부를 해보아야 겠다.

 

3. 코드

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    var stack = [String]()
    var answer = 0
    if cacheSize == 0 {
        return cities.count * 5
    }
    for i in cities {
        if stack.contains(i.lowercased()) {
            answer += 1
            stack.remove(at: stack.firstIndex(of: i.lowercased())!)
            stack.append(i.lowercased())
        } else {
            answer += 5
            if stack.count < cacheSize {
                stack.append(i.lowercased())
            } else {
                stack.removeFirst()
                stack.append(i.lowercased())
            }
        }
    }
    return answer
}