[Swift Algorithm] 프로그래머스 17680 캐시 (2018 카카오 블라인드)

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

코딩테스트 연습 - [1차] 캐시

 

먼저 대소문자를 구분하지않는다에서 문자열을 모두 lowercase로 변형했구요

 

LRU(Least Recently Used)가 적용되는 방식이에요

최근에 사용하지 않았던 파일을 교체하는 방식이에요

캐시메모리가 3일경우 1 -> 2 -> 3 -> 1 -> 4 순으로 접근한다면

[1] -> [1,2] -> [1,2,3] -> a:[1,2,3] -> b:[1,4,3] 이렇게 변할거에요

a에서 1이 한번더 사용되면서 제일 최근에 사용하지않은 파일은 2가 됬구요

그상태에서 4가 들어오면서 4가 2의자리에 들어가게 되는 원리에요

 

 

파일의 최신상태를 구별할 변수를 하나 만들어두고

파일을 접근할때마다 변경해줄거에요

1번파일: 1

2번파일: 2

3번파일: 3

1번파일: 4

4번파일: 5

이런 순서로 넣어줄거에요

그러면 위와같이 교체할때

괄호는 최근사용시기를 나타낸다고하면

[1(4), 2(2), 3(3)]이니까 

2가 최근에 사용되지않았으니 2를 제거하고 4(5)를 넣어주면될거에요

이런 방식으로 접근했어요

 

 

func solutionP17680(_ cacheSize:Int, _ cities:[String]) -> Int {
    
    let cities = cities.map{$0.lowercased()}
    var cache: [String: Int] = [:]
    var result = 0
    var order = 0
    
    if cacheSize == 0 {
        return cities.count * 5
    }
    
    for city in cities {
        order += 1
        
        if cache.keys.contains(city) {
            cache[city]! = order
            result += 1
        } else {
            if cache.count >= cacheSize {
                var leastRecentKey: String = ""
                var minNum = 9999999
                for (key, value) in cache {
                    if value < minNum {
                        leastRecentKey = key
                        minNum = value
                    }
                }
                cache.removeValue(forKey: leastRecentKey)
            }
            cache[city] = order
            result += 5
        }
    }
    
    return result
}