146. LRU Cache ☆☆★★★ (OrderedDict 사용!!)

146. LRU Cache

 

evict       the least   recently used key
제거하다, 가장 적게, 최근에,   사용된

=> Least Recently Used "가장 오랫동안 안 쓴 것" 을 삭제

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = {}

        # evict the least recently used key:
        # 제거하다, 가장 적게, 최근에, 사용된
        # Least Recently Used (가장 오랫동안 안 쓴 것) 을 삭제
        self.oldest_key = [] # 가장 오래된건 self.oldest_key[0] 으로 가게.
        
    def move_to_end(self, key):
        # 사용한 키는 다시 제일 위로
        self.oldest_key.remove(key)
        self.oldest_key.append(key) 

    def get(self, key: int) -> int:
        if key in self.data:
            # 사용한 키는 다시 제일 위로
            self.move_to_end(key)
            return self.data[key]
        else:
            return -1
        

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data[key] = value
            # 사용한 키는 다시 제일 위로
            self.move_to_end(key)
        else: # 키가 없으면
            if len(self.data.keys()) < self.capacity: # 용량 안찼으면
                self.data[key] = value 
                # 새로운 키도 self.oldest_key에 추가
                self.oldest_key.append(key)
            else:
                # 용량 찼으면, 가장 오래된 키 삭제하고. 추가
                oldest = self.oldest_key[0]
                self.oldest_key.remove(oldest)
                del self.data[oldest]
                
                self.oldest_key.append(key)
                self.data[key] = value 
      

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

 

코드 전체 구조는 괜찮게 잘 짜셨어요!
그런데 약간만 고치면 조금 더 깔끔하고 정확해질 수 있어요. 수정할 부분만 짚어드릴게요.

---

1. len(self.data.keys()) 대신 len(self.data) 쓰기

• self.data.keys() 는 dict_keys 객체를 생성하기 때문에, 그냥 len(self.data) 쓰는게 더 깔끔하고 빠릅니다.

if len(self.data) < self.capacity:

---

2. remove(oldest) 대신 pop(0) 써도 됨

• self.oldest_key는 항상 가장 오래된 키가 0번 인덱스에 오니까
• self.oldest_key.remove(oldest) 말고 그냥 self.oldest_key.pop(0) 해버리면 더 직관적입니다.

oldest = self.oldest_key.pop(0)
del self.data[oldest]

(참고로 remove()는 값을 찾아서 삭제하는 거라, 인덱스 알고 있으면 pop()이 더 빠르고 명확합니다.)

cf. 비교

self.oldest_key.pop()  : self.oldest_key[-1] 제거

self.oldest_key.pop(0)  : self.oldest_key[0] 제거

---

3. 참고만: 성능 개선할 거면

• self.oldest_key를 deque로 만들면 popleft() 쓸 수 있어서 더 빨라요. (from collections import deque)
• 하지만 지금 문제에서는 리스트로 해도 괜찮습니다.

---

요약해서 수정하면 이렇게 됩니다:

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = {}
        self.oldest_key = []

    def move_to_end(self, key):
        self.oldest_key.remove(key)
        self.oldest_key.append(key)

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

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data[key] = value
            self.move_to_end(key)
        else:
            if len(self.data) < self.capacity:
                self.data[key] = value
                self.oldest_key.append(key)
            else:
                oldest = self.oldest_key.pop(0)
                del self.data[oldest]
                self.data[key] = value
                self.oldest_key.append(key)

 

1. deque 버전 (큐처럼 빠르게 pop(0))

deque는 양쪽에서 삽입/삭제 O(1) 로 됩니다.
리스트는 pop(0)이 느린데, deque는 popleft() 하면 빠릅니다.

from collections import deque

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = {}
        self.oldest_key = deque()  # 리스트 대신 deque 사용

    def move_to_end(self, key):
        self.oldest_key.remove(key)
        self.oldest_key.append(key)

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

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data[key] = value
            self.move_to_end(key)
        else:
            if len(self.data) < self.capacity:
                self.data[key] = value
                self.oldest_key.append(key)
            else:
                oldest = self.oldest_key.popleft()  # 맨 앞에서 빠르게 제거
                del self.data[oldest]
                self.data[key] = value
                self.oldest_key.append(key)

✅ 여기까지 하면 popleft()가 빠르니까 성능 살짝 좋아짐!

---

2. 진짜 O(1) 버전 (OrderedDict 사용)

• OrderedDict는 삽입 순서 기억하는 딕셔너리.
• move_to_end(), popitem()을 쓰면 get, put 모두 O(1) 입니다.
• 이게 인터뷰에서도 제일 좋은 답변입니다.

 

OrderedDict()

 

제일 뒤로 이동

- move_to_end(키)

 

키 데이터 제거

- popitem(last=False) 제일앞

-  popitem(제일뒤)

-  pop(키) 

코드:

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = OrderedDict() # 그냥 dict 대신 OrderedDict, OrderedDict는 항상 새로운 값 추가하면, 맨 뒤로 보내줌
        
    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        
        """        
        # 사용한 키는 제일 뒤로
        get 시에도. 잊어버리지 않게..숙지 필요!!
        """
        self.data.move_to_end(key) 
        return self.data[key]
        

    def put(self, key: int, value: int) -> None:
        # OrderedDict는 항상 새로운 값 추가하면, 맨 뒤로 보내줌
        if key in self.data:  # 그래서, 키가 있으면
            self.data.move_to_end(key) # 맨뒤로 보내고
        self.data[key] = value # 추가. <-- 여기서 새롭게 추가됬으면, 그냥 바로 제일 뒤로 추가됨        
        
        if len(self.data) > self.capacity: # 용량 넘으면
            # 가장 오래된거 삭제, (FIFO 방식)
            self.data.popitem(last=False)        


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

 

 

• OrderedDict는 새로운 키를 추가할 때 항상 맨 뒤에 넣어줘.
• 그래서 새 키를 넣으면 따로 move_to_end 안 해도 "맨 뒤"에 이미 가 있음.

 

---

요약

방법시간복잡도특징

list 사용	get: O(1), put: O(N) (remove 때문에)	느림
deque 사용	get: O(N), put: O(1) (remove 때문에 여전히 N)	약간 개선
OrderedDict 사용	get: O(1), put: O(1)	✅ 베스트

---

추가 꿀팁

面접에서

"LRU Cache를 O(1)로 만들 수 있어?"

→ "네, OrderedDict 쓰면 get, put 모두 O(1)로 됩니다."