[LeetCode] 460. LFU Cache

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

LFU Cache - LeetCode

key, value 값을 저장해야해서 map을 사용해야겠다고 생각했다.

그래서, key, value 저장 map 하나와 key, user counter를 저장 할 map을 각각 선언해서 풀려고 했는데, 일부 테스트케이스에서 막힌다. 

class LFUCache {
    private Map<Integer, Integer> cache;	    // key, value
    private Map<Integer, Integer> counter;	    // key, counter
    private int capacity;

    public LFUCache(int capacity) {
        // Initializes the object with the capacity of the data structure.
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        counter = new HashMap<>(capacity);
    }

    public int get(int key) {
        // return value of key if the key exists in the cache or return -1
        // System.out.println("this time key is? "+key);
        // System.out.println("now cache contains this key? "+cache.containsKey(key));
        
        if (cache.containsKey(key)){
            counter.put(key, counter.get(key)+1);
            // System.out.println("now this value of key("+key+") = "+cache.get(key));
            return cache.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if (capacity != 0){
            // 캐시가 capacity에 도달하면, 가장 적게 사용된 키를 삭제함 (use counter가 적은 key)
            // inserting a new item
            if (!cache.containsKey(key) && cache.size() == capacity){
                int lfuKey = Collections.min(counter.entrySet(), Map.Entry.comparingByValue()).getKey();
                // System.out.println("Lfu : "+lfuKey);
                cache.remove(lfuKey);
                counter.remove(lfuKey);
                // System.out.println("delete "+lfuKey+" from the cache! contains key?"+cache.containsKey(lfuKey));
            }
            // Update the value of the key if present
            // or inserts the key if not already present
            // insert되면 user counter : 1로 세팅
            // System.out.println("now key = "+key);
            cache.put(key, value);
            if (counter.containsKey(key)){
                counter.put(key, counter.get(key)+1);
            } else {
                counter.put(key, 1);
            }
            // System.out.println("now cache !? "+cache);
        }
    }
}

now key = 2
now cache !? {2=1}
now key = 3
now cache !? {2=1, 3=2}
this time key is? 3
now cache contains this key? true
now this value of key(3) = 2
this time key is? 2
now cache contains this key? true
now this value of key(2) = 1
Lfu : 2
delete 2 from the cache! contains key?false
now key = 4
now cache !? {4=3, 3=2}
this time key is? 2
now cache contains this key? false
this time key is? 3
now cache contains this key? true
now this value of key(3) = 2
this time key is? 4
now cache contains this key? true
now this value of key(4) = 3

---

테스트 케이스

["LFUCache","put","put","get","get","put","get","get","get"]
[[2],[2,1],[3,2],[3],[2],[4,3],[2],[3],[4]]

 

Output : [null,null,null,2,1,null,-1,2,3]

Expected : [null,null,null,2,1,null,1,-1,3]

 

✳ 

When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

 

알아냈다. user counter가 같은 경우 사용된지가 오래된 key를 삭제해야하는데, 나는 최근 사용한 키(?) 먼저 생성된 키(?) 가 삭제되어서 테스트케이스를 통과하지 못한 것.