(LeetCode) 146. LRU Cache

The link : leetcode.com/problems/lru-cache/

LRU Cache - LeetCode

문제 자체가 굉장히 직관적이므로, 문제를 따라 시뮬레이션을 구현해주면 된다.

 

class LRUCache {
    int cap = 0, time = 0;
    map<int, pair<int,int>> cache; // key, value, 사용된 횟수

public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if(cache.empty()||!cache.count(key)) return -1;
        cache[key].second = ++time;
        return cache[key].first;
    }
    
    void put(int key, int value) {
        if(cache.count(key)){ // 기존에 있던거 업데이트
            cache[key] = {value, time++}; return;
        }
        if(cache.size()==cap){
            int temp_key = 0;
            int temp_num = INT_MAX;
            for(auto temp : cache){
                if(temp_num>temp.second.second){
                    temp_key = temp.first;
                    temp_num = temp.second.second;
                }
            }
            cache.erase(temp_key);
        }
        cache[key] = {value, ++time};
    }
};

Map을 구현하여 풀었다. 

단, 한가지 the Least Recently Used (LRU) Cache를 제거하기 위해 time이라는 변수를 세웠다. 

이 time 변수는 전역 변수로, 어떠한 캐쉬에 행동이 주어질 경우 무조건 +1이된 time을 사용된 횟수로 저장했다. 

이를 토대로 사용된 횟수들을 비교하여 제거해야할 LRU Cache를 선별했다.