파비의 매일매일 공부기록

2023.01.29 Today's Challenge 본문

Problem Solving/LeetCode

2023.01.29 Today's Challenge

fabichoi 2023. 1. 29. 23:45

https://leetcode.com/problems/lfu-cache/

 

LFU Cache - LeetCode

LFU Cache - Design and implement a data structure for a Least Frequently Used (LFU) [https://en.wikipedia.org/wiki/Least_frequently_used] cache. Implement the LFUCache class: * LFUCache(int capacity) Initializes the object with the capacity of the data str

leetcode.com

소스가 상당히 김.
LRU 캐시는 운영체제 쪽 배울때 있던 내용인거 같은데..

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.used = 0
        self.cache_key = dict()
        self.cache_orderedCount = dict()
        self.min_cnt = 0        

    def get(self, key: int) -> int:
        val = -1
        if key in self.cache_key:
            val = self.cache_key[key][0]
            old_cnt = self.cache_key[key][1]
            self.cache_key[key][1] += 1
            del self.cache_orderedCount[old_cnt][key]
            new_cnt = self.cache_key[key][1]
            self._updateCacheCountDict(key, val, new_cnt)

            if self.min_cnt == old_cnt and len(self.cache_orderedCount[old_cnt]) == 0:
                self.min_cnt = new_cnt
        return val
        

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        
        if key in self.cache_key:
            self.cache_key[key][0] = value
            old_cnt = self.cache_key[key][1]
            self.cache_key[key][1] += 1
            new_cnt = old_cnt + 1
            del self.cache_orderedCount[old_cnt][key]
            self._updateCacheCountDict(key, value, new_cnt)

            if self.min_cnt == old_cnt and len(self.cache_orderedCount[old_cnt]) == 0:
                self.min_cnt = new_cnt
            
        else:
            if self.used < self.capacity:
                self.cache_key[key] = [value, 1]
                self._updateCacheCountDict(key, value, 1)
                self.used += 1
                self.min_cnt = 1
            else:
                rm_key, rm_val = self.cache_orderedCount[self.min_cnt].popitem(0)
                del self.cache_key[rm_key]
                self.cache_key[key] = [value, 1]
                self._updateCacheCountDict(key, value, 1)
                self.min_cnt = 1
    
    def _updateCacheCountDict(self, key, value, new_cnt):
        if new_cnt not in self.cache_orderedCount:
            self.cache_orderedCount[new_cnt] = OrderedDict()
        self.cache_orderedCount[new_cnt][key] = value
        self.cache_orderedCount[new_cnt].move_to_end(key)
        


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

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.01.31 Today's Challenge  (0) 2023.01.31
2023.01.30 Today's Challenge  (1) 2023.01.30
2023.01.28 Today's Challenge  (0) 2023.01.28
2023.01.27 Today's Challenge  (0) 2023.01.27
2023.01.26 Today's Challenge  (0) 2023.01.26
Comments