[LeetCode] 460번 LFU Cache 문제를 풀어보았다. (ft. java)

2023년 01월 29일 일요일 - 허허 이렇게 늦은 시간에 글을 쓰다니...

오늘 올려볼 문제는 460번 LFU Cache 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

유지보수 안할거라고 블로그 자동화 대충 만들어놓았던 나를 후회한다....

입력

사진에서도 볼 수 있듯이 다양한 파라매터가 입력으로 들어온다.

---

풀이 및 코드

LFU Cache를 구현하는 문제이다.

기본적으로 capacity를 받아서 최대로 저장할 수 있는 캐시의 양을 받는다.

이후 put또는 get 메소드를 통해서 cache에 접근하고 값을 추가하는데 아래와 같은 규칙을 따른다.

put을 통해서 캐시에 k-v 형태로 값을 넣는다.

이 때 캐시의 capacity가 넘어가게 되면 cnt(key)값이 가장 작은 값을 지우고 새로운 값을 넣는다.

이 때 cnt(key)의 값이 같은 key들이 여러개 존재한다면 가장 오래전에 쓰인 값을 지운다.

cnt(key)가 올라가는 기준은 get, put 메소드에 불릴 때 마다이다.

오늘은 처음부터 정답을 생각해냈다.

1. 캐시의 k-v 값을 저장할 hashmap
2. key의 cnt값을 저장할 hashmap
3. cnt값을 key로 두고 해당 cnt를 가지고 있는 키를 순서대로 저장하고 있을 treemap

이 세가지를 사용했다. 자세한 사항은 구현을 보면 알 수 있을 것이다.

이제 코드를 봐보자!

풀이코드

class LFUCache {
    int capacity, minCnt = 0;
    HashMap<Integer, Integer> cnt = new HashMap<>();
    TreeMap<Integer, LinkedHashSet<Integer>> lru = new TreeMap<>();
    HashMap<Integer, Integer> cache = new HashMap<>();
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)) return -1;
        
        int prevCnt = cnt.get(key), nowCnt = prevCnt + 1;
        cnt.put(key, nowCnt);
        
        lru.get(prevCnt).remove(key);
        if(lru.get(prevCnt).isEmpty()) lru.remove(prevCnt);
        
        if(!lru.containsKey(nowCnt)) lru.put(nowCnt, new LinkedHashSet<>());
        lru.get(nowCnt).add(key);
        
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        if(capacity == 0) return;
        if(!cache.containsKey(key) && capacity == cache.size()) {
            int minCnt = lru.firstKey(), minKey = -1;
            var itr = lru.get(minCnt).iterator();

            if(itr.hasNext()) minKey = itr.next();
            
            cache.remove(minKey);
            lru.get(minCnt).remove(minKey);
            cnt.remove(minKey);
        }
        
        int prevCnt = cnt.getOrDefault(key, 0), nowCnt = prevCnt + 1;
        cache.put(key, value);
        cnt.put(key, nowCnt);
        
        if(lru.get(prevCnt) != null) {
            lru.get(prevCnt).remove(key);
            if(lru.get(prevCnt).isEmpty()) lru.remove(prevCnt);
        }
        
        if(!lru.containsKey(nowCnt)) lru.put(nowCnt, new LinkedHashSet<>());
        lru.get(nowCnt).add(key);
    }
}

---

제출 화면

어려워보였지만 풀어서 뿌듯한 마음에 블로그를 올리고 싶었다!!

다만... 내 블로그 자동화는 12시가 넘어가면 작동하지 않기에 이를 수정하려다가... 너무 시간이 오래걸려서 거의 2시가 되었다..

내일은 좀 힘들 것 같다...

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.