문제 링크 (opens new window)

문제 설명

1. LRU 캐시 알고리즘은 가장 최근에 사용되지 않은 데이터를 먼저 삭제하는 알고리즘이다.
2. 캐시 데이터를 딕셔너리로 관리하고, 버퍼에 최근 접근한 데이터 키값을 순서대로 구현한다.
3. 배열 0번째에 insert하는 연산이 시간 소요가 너무 심함.

class LRUCache {
    var capacity: Int
    var cache: [Int: Int] = [:]
    private var buffer: [Int] = []

    init(_ capacity: Int) {
        self.capacity = capacity
    }

    func get(_ key: Int) -> Int {
        if let value = self.cache[key] {
            // 접근 업데이트
            if buffer.contains(key) {
                buffer.removeAll(where: {$0 == key})
                buffer.insert(key, at: 0)
            } else {
                buffer.insert(key, at: 0)
            }
            if buffer.count > self.capacity {
                let removeKey = buffer.removeLast()
                if removeKey != key {
                    self.cache.removeValue(forKey: removeKey)
                }
            }
            return value
        } else {
            return -1
        }
    }

    func put(_ key: Int, _ value: Int) {
        // 접근 업데이트
        if buffer.contains(key) {
            buffer.removeAll(where: {$0 == key})
            buffer.insert(key, at: 0)
        } else {
            buffer.insert(key, at: 0)
        }
        if buffer.count > self.capacity {
            let removeKey = buffer.removeLast()
            self.cache.removeValue(forKey: removeKey)
        }
        cache[key] = value
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * let obj = LRUCache(capacity)
 * let ret_1: Int = obj.get(key)
 * obj.put(key, value)
 */

개선 코드

1. 양방향 연결리스트로 성능 개선

class ListNode {
    var prev: ListNode?
    var next: ListNode?
    var value = 0
    var key = 0
}

class LRUCache {
    private var capacity: Int
    private var cache: [Int: ListNode] = [:]
    private var head: ListNode
    private var tail: ListNode

    init(_ capacity: Int) {
        self.capacity = capacity
        head = ListNode()
        tail = ListNode()

        head.next = tail
        tail.prev = head
    }

    // private func getNode(_ key: Int) -> ListNode?
    private func getNode(_ key: Int) -> ListNode? {
        guard let node = cache[key] else { return nil }
        makeHead(node)
        return node
    }

    // private func makeHead(_ node: ListNode)
    private func makeHead(_ node: ListNode) {
        node.prev?.next = node.next
        node.next?.prev = node.prev

        node.next = head.next
        node.next?.prev = node

        head.next = node
        node.prev = head
    }

    // private func createNode(_ key: Int, _ value: Int)
    private func createNode(_ key: Int, _ value: Int) {
        let node = ListNode()
        node.value = value
        node.key = key

        cache[key] = node

        makeHead(node)
    }

    func get(_ key: Int) -> Int {
        guard let listNode = getNode(key) else { return -1 }
        return listNode.value
    }

    func put(_ key: Int, _ value: Int) {
        if let listNode = getNode(key) {
            listNode.value = value
            return
        }
        createNode(key, value)

        if cache.count > self.capacity, let last = tail.prev {
            tail.prev = last.prev
            last.prev?.next = tail

            cache[last.key] = nil
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * let obj = LRUCache(capacity)
 * let ret_1: Int = obj.get(key)
 * obj.put(key, value)
 */