LeetCode 146(LRU Cache, Python)

1. 문제 링크

• LRU Cache - LeetCode

LRU Cache - LeetCode

2. 문제 설명

• 주어진 연산을 수행하는 LRU(Least Recently Used) 캐시를 구현하기
• LRU 캐시가 지원해야하는 두 가지 연산은 다음과 같다. 
  1. get(key): 캐시에서 특정 키(key)에 대응하는 값 반환(사용O). 만약 해당 키가 캐시에 없다면 -1을 반환(이건 사용X).
  2. put(key, value): 캐시에 값을 입력(사용O). 만약 캐시가 가득 차 있으면, 가장 오랫동안 사용되지 않은(Least Recently Used) 항목을 제거하고 새로운 값을 삽입

3. 처음 풀이

• get 메서드는 주어진 키를 찾아 해당 값을 가져오기. 키가 존재하면 해당 키-값 쌍을 memo에서 삭제 후 다시 추가하여 최근 사용된 것으로 갱신
• put 메서드는 주어진 키-값을 memo에 추가. 이미 존재하는 키라면 해당 키-값 쌍을 삭제 후 새로운 값을 추가하여 최근 사용된 것으로 갱신. 또한, 캐시의 크기가 용량을 초과하면 가장 오래된 항목을 삭제
• 이때, 일반적인 dictionary를 사용해도 되지만 이전 버전의 파이썬에서는 dictionary의 순서가 보장되지 않기 때문에 순서가 있는 딕셔너리임을 명시적으로 밝혀주기 위해 OrderedDict을 사용하였음.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        # OrderedDict를 사용하여 키-값 쌍을 유지하는 memo 초기화
        self.memo = OrderedDict()
        # 캐시의 최대 크기 설정
        self.capacity = capacity

    def get(self, key: int) -> int:
        # 주어진 키가 memo에 없으면 -1 반환
        if key not in self.memo:
            return -1
        # 키에 해당하는 값을 가져와서 해당 키-값 쌍을 memo에서 제거 후 다시 추가 (갱신)
        value = self.memo[key]
        del self.memo[key]
        self.memo[key] = value
        return self.memo[key]
            
    def put(self, key: int, value: int) -> None:
        # 이미 존재하는 키라면 해당 키-값 쌍을 삭제
        if key in self.memo:
            del self.memo[key]
        # 새로운 키-값 쌍을 memo에 추가
        self.memo[key] = value
        # 캐시의 크기가 용량을 초과하면 가장 오래된 항목 삭제
        if len(self.memo) > self.capacity:
            del self.memo[next(iter(self.memo))]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

4. 다른 풀이

• OrderedDict.move_to_end(key) 메소드를 이용하면 삭제 후 추가하지 않아도 최근 요소로 갱신이 가능하다.
• popitem()은 기본적으로 후입선출 방식이지만 인자에 False를 전달하면 선입선출이 가능하다.

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dict = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        
        self.dict.move_to_end(key)
        return self.dict[key]

    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            self.dict.move_to_end(key)
        
        self.dict[key] = value
        if len(self.dict) > self.capacity:
            self.dict.popitem(False)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

5. 배운 점

• OrderedDict
  • OrderedDict는 파이썬의 내장 모듈인 collections에서 제공되는 클래스, 순서가 있는 딕셔너리
  • 일반적인 딕셔너리는 파이썬 3.7 이전의 버전에서는 순서가 보장되지 않음
  • 그러나 파이썬 3.7 이상에서는 일반 딕셔너리도 삽입 순서를 유지. 그럼에도 다른 차이점이 있음. 
  • OrderedDict 만의 메서드가 있다. 예를들어 move_to_end() 메서드를 사용하여 특정 항목을 딕셔너리의 끝으로 이동시킬 수 있음.
  • Equality 검사를 할 때 일반 dictionary는 요소의 값의 일치만 확인하며, OrderedDict은 순서까지 동등성을 확인함.

  from collections import OrderedDict
  
  # 일반적인 딕셔너리
  normal_dict = {'banana': 3, 'apple': 1, 'orange': 2}
  print("Normal Dict:", normal_dict)  # 출력 결과: {'banana': 3, 'apple': 1, 'orange': 2}
  
  # OrderedDict
  ordered_dict = OrderedDict([('banana', 3), ('apple', 1), ('orange', 2)])
  print("OrderedDict:", ordered_dict)  # 출력 결과: OrderedDict([('banana', 3), ('apple', 1), ('orange', 2)])
  
  # 항목 추가
  normal_dict['grape'] = 4
  ordered_dict['grape'] = 4
  
  print("\\nAfter Adding 'grape':")
  print("Normal Dict:", normal_dict)  # 출력 결과: {'banana': 3, 'apple': 1, 'orange': 2, 'grape': 4}
  print("OrderedDict:", ordered_dict)  # 출력 결과: OrderedDict([('banana', 3), ('apple', 1), ('orange', 2), ('grape', 4)])
  
  # move_to_end 메서드 사용
  ordered_dict.move_to_end('apple')  # 'apple' 항목을 끝으로 이동
  
  print("\\nAfter Moving 'apple' to the End in OrderedDict:")
  print("OrderedDict:", ordered_dict)  # 출력 결과: OrderedDict([('banana', 3), ('orange', 2), ('grape', 4), ('apple', 1)])
  
  # Equality 검사
  equal_check = normal_dict == dict(ordered_dict)
  print("\\nEquality Check:", equal_check)  # 출력 결과: False
  
  

 

• next(iter())는 두 가지 함수를 조합하여 사용하는 구문
  1. iter() 함수: 객체를 이터레이터로 변환
  2. next() 함수: 이터레이터에서 다음 값을 가져옴. 만약 끝에 도달했다면 StopIteration 예외가 발생, 이때 두 번째 인수로 전달된 기본 값이 있으면 그 값을 반환

  my_list = [1, 2, 3, 4, 5]
  my_iterator = iter(my_list)
  
  # 첫 번째 호출
  result1 = next(my_iterator)
  print(result1)  # 출력 결과: 1
  
  # 두 번째 호출
  result2 = next(my_iterator)
  print(result2)  # 출력 결과: 2

 

• popitem() 메서드는 딕셔너리에서 항목을 제거하고 반환, 일반적으로 인자 없이 사용. 하지만 파이썬 3.9부터는 last=True(기본값) 또는 last=False를 인자로 사용 가능. True(기본값)은 후입선출, False는 선입선출