146. LRU Cache

문제 링크: https://leetcode.com/problems/lru-cache/

LRU Cache - LeetCode

간단한(?) LRU Cache를 구현하는 문제. 나는 CS를 정말 1도 모르기 때문에 이게 뭔지부터 공부하고 문제를 풀었다. 스택처럼 캐시가 쌓이는데, 용량을 넘어가면 "가장 오래 전에 사용한" 것부터 날린다.

  - 즉 조회, 생성이 이루어지면 사용된 것으로 간주해야 한다.

 

LRU Cache에 대한 자세한 설명은 좋은 블로그들 많으니 넘기고...

 

조회, 생성에 해당하는 get, put 함수를 O(1)에 구현해야 하는데, 이 말인즉슨 리스트 내 어떤 키값을 빼서 가장 앞으로 옮기는 작업을 O(1)에 처리해야 한다는 것이다. 당연히 단순 리스트로는 안되고, doubly linked list를 사용하면 된다. 파이썬으로 이를 구현하려면 front, back을 가리키는 포인터(해당 키값)가 저장되어있는 리스트 또는 딕셔너리를 사용할 수 있다. 리스트를 사용하면 다음과 같이 코드를 짤 수 있다.

 

뭔가 길다. 이와 비슷하게 doubly linked list를 써야 하는 코테 기출 문제들이 몇 개 있다.

  - 2021 카카오 채용연계형 인턴십 문제 - 표 편집

  - 2022 삼성 SW역량테스트 오전 2번 문제 복원본

  - 2022 삼성 SW역량테스트 오후 2번 문제 복원본

 

그런데 파이썬에는? 무려 내장 라이브러리인 collections 내에 OrderedDict라는 친구가 있다. 그러니까 딕셔너리인데 순서가 존재하고... 존재하는 키를 가장 앞 또는 뒤로 매우 빠르게 옮길 수 있다. 모든 doubly linked list 문제를 OrderedDict로 풀 수는 없지만 LRU Cache 같은 경우는 이동해야하는 위치가 무조건 한 쪽 끝이기 때문에 OrderedDict로 날먹이 가능하다. 한 쪽 끝으로 옮기는 move_to_end 메서드와 한 쪽 끝 키값을 제거하는 popitem 메서드를 이용하면 다음과 같이 간단하게 문제를 풀 수 있다.

직접 구현하는 것보다 시간도 공간도 덜 차지한다. 리스트 말고 딕셔너리로 구현했으면 공간은 비슷하게 나올 것 같긴 하다. 

 

...좋은 거 있으면 잘 써먹자.