460. LFU Cache

class LFUCache {

    private final int capacity;

    // <key, value>
    Map<Integer, Integer> cache = new HashMap<>();

    // <key, frequency>
    Map<Integer, Integer> frequencyMap = new HashMap<>();

    // <frequency, <key>>
    Map<Integer, LinkedHashSet<Integer>> accessSequenceMap = new HashMap<>();

    // <frequency> : 현존하는 frequency 를 저장
    Set<Integer> frequencySet = new HashSet<>();

    public void expireCache() {
        Integer smallestFrequency = null;
        for (Integer frequency : frequencySet) {
            if (smallestFrequency == null) {
                smallestFrequency = frequency;
            } else {
                if (frequency < smallestFrequency) {
                    smallestFrequency = frequency;
                }
            }

        }

        LinkedHashSet<Integer> smallestFrequencyKeys = accessSequenceMap.get(smallestFrequency);
        Integer lastAccessedKey = null;
        for (Integer key : smallestFrequencyKeys) {
            lastAccessedKey = key;
        }

        // Expire Target Key
        cache.remove(lastAccessedKey);
        frequencyMap.remove(lastAccessedKey);
        smallestFrequencyKeys.remove(lastAccessedKey);
        if (smallestFrequencyKeys.isEmpty()) {
            frequencySet.remove(smallestFrequency);
        }
    }

    public void updateFrequency(int key) {
        Integer frequency = frequencyMap.get(key);
        if (frequency == null) {
            // first access
            frequency = 0;
        } else {
            if (accessSequenceMap.get(key).size() == 1) {
                // 해당 frequency 에 해당 키만 존재
                frequencySet.remove(key);
            }
            accessSequenceMap.get(frequency).remove(key);
        }
        frequency++;

        frequencySet.add(frequency);
        frequencyMap.put(key, frequency);

        LinkedHashSet<Integer> newFrequencySet = accessSequenceMap.get(frequency);
        if (newFrequencySet == null) {
            newFrequencySet = new LinkedHashSet<>();
        }
        newFrequencySet.add(key);
        accessSequenceMap.put(frequency, newFrequencySet);
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Integer value = cache.get(key);
        if (value != null) {
            updateFrequency(key);
            return value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (this.capacity == cache.size()) {
            expireCache();
        }
        cache.put(key, value);
    }
}