Programmers Lv2) 캐시

출처: programmers.co.kr/learn/courses/30/lessons/17680

분류: Lv2

---

접근방식

LRU(Least Recently Used)의 개념을 알면 쉽게 풀 수 있는 문제입니다.
LRU란 캐시를 관리하는 방법인데요, 캐시를 비울 때 가장 오래 사용되지 않은 녀석을 지우는 방식입니다.

만약 캐시의 크기가 4이고, [1, 2, 3, 4] 가 들어있을 때,
2가 추가로 들어온다면 2가 가장 최신에 사용된 것이 되므로 캐시는 [1, 3, 4, 2]로 변하게 됩니다.

만약 도시가 이미 캐시에 들어있다면 cache hit 이 되어 시간 1이 추가되고,
캐시에 없다면 chache miss가 되어 5가 추가됩니다.

저는 처음에 시간 복잡도를 생각해서 링크드 리스트와 딕셔너리를 섞어서 굉장히 복잡하게 풀었는데...
캐시 사이즈가 최대 30밖에 되지 않으므로 배열로 그냥 문제 그대로 풀어도 타임아웃이 나지 않더라구요.. 하핳... 

해결방법

접근방식에서 말씀드린 그대로,

도시가 캐시에 포함되어 있으면 시간을 1만큼 증가시키고 캐시에 들어있는 도시를 맨 뒤로 보내줍니다.

포함되어 있지 않다면, 도시를 캐시의 맨 뒤에 추가하고 캐시 사이즈가 max를 넘어섰다면 맨 앞의 원소를 지워줍니다.

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    let cacheHit = 1
    let cacheMiss = 5
    var cacheList = [String]()
    var excuteTime = 0
    
    for city in cities {
        let city = city.lowercased()
        if cacheList.contains(city) {
            excuteTime += cacheHit
            cacheList.remove(at: cacheList.firstIndex(of: city)!)
            cacheList.append(city)
        } else {
            excuteTime += cacheMiss
            cacheList.append(city)
            if cacheList.count > cacheSize {
                cacheList.removeFirst()
            }
        }
    }
    
    return excuteTime
}

 

링크드 리스트를 만들어 풀어본 풀이입니다.

class CacheList {
    class Cache {
        var value: String
        weak var previous: Cache?
        var next: Cache?
        
        init(value: String) {
            self.value = value
        }
    }
    
    var table = [String:Cache]()
    var head: Cache?
    var tail: Cache?
    var count = 0
    
    func append(value: String) {
        guard let _ = head else {
            head = Cache(value: value)
            tail = head
            table[value] = head
            return
        }
        let newNode = Cache(value: value)
        tail?.next = newNode
        newNode.previous = tail
        tail = newNode
        table[value] = newNode
    }
    
    func delete(node: Cache) {
        let prev = node.previous
        let next = node.next

        prev?.next = next
        next?.previous = prev
        table[node.value] = nil
        if node.value == tail?.value {
            tail = tail?.previous
        }
        node.previous = nil
        node.next = nil
    }
    
    func removeHead() {
        guard let head = head else { return }
        self.head = head.next
        table[head.value] = nil
        
    }
    
    func moveToTail(from cache: Cache) {
        guard cache.value != tail?.value else { return }
        if head?.value == cache.value {
            head = head?.next
        }
        
        let prev = cache.previous
        let next = cache.next
        prev?.next = next
        next?.previous = prev
        
        cache.next = nil
        cache.previous = tail
        tail?.next = cache
        tail = cache

    }
}


func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    let cacheHit = 1
    let cacheMiss = 5
    let cacheList = CacheList()
    var excuteTime = 0
    
    for city in cities {
        let city = city.lowercased()
        if let cache = cacheList.table[city] {
            excuteTime += cacheHit
            cacheList.moveToTail(from: cache)
        } else {
            excuteTime += cacheMiss
            cacheList.append(value: city)
            if cacheList.table.count > cacheSize {
                cacheList.removeHead()
            }
        }
    }

    return excuteTime
}

 

배운점

처음에 왜 이렇게 어렵게 접근했을까요?!!

초기엔 일단 문제 그대로 러프하게 접근해보고 개선해나가는 것이 시간을 줄이는 길인 것 같습니다.