[LeetCode 해석 및 풀이] 146. LRU Cache

LeetCode 문제 해석 및 풀이 방법

 

문제 146. LRU Cache(LRU 캐시)

바로가기

 

문제 설명

영문

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

 

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key
• value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

 

The functions get and put must each run in O(1) average time complexity.

한글

 

제한조건

•  

 

입출력 예

입력	출력

 

 

해답 및 해설

LRU는 페이지 교체 알고리즘 중 하나로, 페이지 교체 알고리즘에는 다음과 같은 3가지가 있다고 한다

• FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법
  단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있음.
• LFU : 가장 적은 횟수를 참조하는 페이지를 교체
  단점 : 참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생
• LRU : 가장 오랫동안 참조되지 않은 페이지를 교체
  단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생

파이썬 (Python)

첫번째 시도(실패)

처음에는 연결리스트만으로, 두번째는 해쉬맵과 함께 리스트, 대큐로, 세번째는 다시 연결리스트와 해쉬맵으로 풀려고 했는데, 통과는 되지만 시간대가 기준에서 너무 벗어나있었다.

 

알고보니 문제에 get, push 메서드가 O(1)의 시간복잡도를 가져야 된다는 조건을 보지 못했었다. 내가 시도한 방법들은 key를 찾는데 O(n)의 시간복잡도가 들어 조건을 만족하지 않는다.

 

코드는 아래에 접어두었다.

class LRUCache:
    def __init__(self, capacity: int):
        self.cur = 0
        self.max = capacity
        self.head = None
        self.tail = None

    def get(self, key: int) -> int:
        if self.cur == 0 :
            return -1
        if self.cur == 1:
            if self.head.key == key:
                return self.head.value
            else:
                return -1

        cur_node = self.head
        prev_node = None
        result = None

        while cur_node:
            if cur_node.key == key:
                result = cur_node.value
                if not cur_node.next:
                    pass
                elif prev_node:
                    prev_node.next = cur_node.next
                else:
                    self.head = cur_node.next
                break
            
            prev_node = cur_node
            cur_node = cur_node.next

        if not result is None:
            self.tail.next = cur_node
            self.tail = cur_node
            cur_node.next = None
            return result
        else:
            return -1


    def put(self, key: int, value: int) -> None:
        class Node:
            def __init__(self, key: int, value: int):
                self.key = key
                self.value = value
                self.next = None

        get_result = self.get(key)

        if get_result != -1:
            self.tail.value = value
            return

        new_node = Node(key, value)
        if self.cur < self.max:
            if self.cur == 0:
                self.head = new_node
                self.tail = new_node
            else:
                self.tail.next = new_node
                self.tail = new_node
            self.cur += 1
            return
        
        self.tail.next = new_node
        self.head = self.head.next
        self.tail = new_node
        return

 

첫시도 (해쉬맵을 쓰지 않아 시간초과가 떴다)

 

class LRUCache:

    def __init__(self, capacity: int):
        self.max = capacity
        self.key_list = []
        self.value_dict = {}

    def get(self, key: int) -> int:
        if not key in self.value_dict:
            return -1
        
        if self.key_list[-1] != key:
            self.key_list.remove(key)
            self.key_list.append(key)
        
        return self.value_dict[key]

    def put(self, key: int, value: int) -> None:
        get_result = self.get(key)

        if get_result != -1:
            self.value_dict[key] = value
            return
        
        if len(self.key_list) == self.max:
            del_key = self.key_list.pop(0)
            del self.value_dict[del_key]

        self.key_list.append(key)
        self.value_dict[key] = value
        return

두 번째 시도 (리스트와 딕셔너리를 이용하였다)

 

from collections import deque

class LRUCache:
    def __init__(self, capacity: int):
        self.max = capacity
        self.key_deque = deque()
        self.value_dict = {}

    def get(self, key: int) -> int:
        if not key in self.value_dict:
            return -1
        
        if self.key_deque[-1] == key:
            pass
        elif self.key_deque[0] == key:
            self.key_deque.popleft()
            self.key_deque.append(key)
        else:
            self.key_deque.remove(key)
            self.key_deque.append(key)
        
        return self.value_dict[key]

    def put(self, key: int, value: int) -> None:
        get_result = self.get(key)

        if get_result != -1:
            self.value_dict[key] = value
            return
        
        if len(self.key_deque) == self.max:
            del_key = self.key_deque.popleft()
            del self.value_dict[del_key]

        self.key_deque.append(key)
        self.value_dict[key] = value
        return

세 번째 시도 (맨 앞의 원소를 빼는데 시간이 오래걸리나 싶어서 데큐로 바꾸었다. 리스트에서는 pop(0)의 시간복잡도가 O(N)이지만, 데큐에서는 O(1)이기 때문이다. 하지만 속도면에서는 차이가 없었다)

 

class Node:
    def __init__(self, key: int):
        self.key = key
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cur = 0
        self.max = capacity
        self.head = None
        self.tail = None
        self.hash = {}

    def get(self, key: int) -> int:
        if not key in self.hash:
            return -1

        if self.cur == 1:
            return self.hash[key]

        cur_node = self.head
        prev_node = None

        if self.tail.key == key:
            return self.hash[key]
        elif self.head.key == key:
            self.head = self.head.next
        else:
            while cur_node:
                if cur_node.key == key:
                    prev_node.next = cur_node.next
                    break
                prev_node = cur_node
                cur_node = cur_node.next

        self.tail.next = cur_node
        self.tail = cur_node
        cur_node.next = None
        return self.hash[key]

    def put(self, key: int, value: int) -> None:
        get_result = self.get(key)
        self.hash[key] = value

        if get_result != -1:
            return

        new_node = Node(key)
        if self.cur < self.max:
            if self.cur == 0:
                self.head = new_node
                self.tail = new_node
            else:
                self.tail.next = new_node
                self.tail = new_node
            self.cur += 1
            return
        
        self.tail.next = new_node
        self.tail = new_node
        del self.hash[self.head.key]
        self.head = self.head.next
        return

네번째 시도 (연결리스트를 직접 만들어서 푼 풀이, 역시 시간적으로 차이가 많이 났었다)

 

두 번째 시도

 

나중에 연구해보기