146. LRU Cache

 

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

 

LRU Cache

 

Discussion 에 있는 풀이

class LRUCache {
    using MyList = list<pair<int, int>>;
    using Cache = unordered_map<int, MyList::iterator>;
    
    int maxSize;
    Cache cache;
    MyList myList;
    
    int promote(int key, int value) {
        // assert key exists
        // move to front, O(1)
        myList.erase(cache[key]);
        myList.push_front({key, value});
        
        // replace iterator to new begin
        cache[key] = myList.begin();
        return value;
    }
    
    void evict() {
        // get key from list 
        int key = myList.rbegin()->first;
        myList.pop_back();  
        cache.erase(key);
    }
    
public:
    LRUCache(int capacity) : maxSize(capacity) { }
    
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;

        return promote(key, it->second->second);
    }
    
    void put(int key, int value) {
        // check if the key exists
        auto it = cache.find(key);
        if (it != cache.end()) {
            promote(key, value);   
            return;
        }
        
        // key doesn't exist in the cache
        if (cache.size() == maxSize) {
            evict();
        }
        
        myList.push_front({key, value});
        cache[key] = myList.begin();
    }
};

 

B 풀이

unorded_map 과 deque 를 사용

class LRUCache {
public:
    unordered_map<int, int> my;
    deque<pair<int, int>> dq;   // key, tag 를 기록
    unordered_map<int, int> tagMap;// key 에 대한 최신 tag 를 기록 
    int cp;
    LRUCache(int capacity) {
        cp = capacity;
    }
    int get(int key) {
        // 맵에 들어 있는 원소인 경우
        if (my.count(key) > 0) {
            int tag = tagMap[key]++;
            dq.push_front(make_pair(key, tag));
            return my[key];    
        }
        return -1;
    }
    void put(int key, int value) {
        // 맵에 들어있는 원소인 경우 갱신
        if (my.count(key) > 0) {
            int tag = tagMap[key]++;
            dq.push_front(make_pair(key, tag));
            my[key] = value;
        }
        // 아닌 경우
        else {
            int tag = tagMap[key]++;
            dq.push_front(make_pair(key, tag));
            my[key] = value;
            if (my.size() > cp) {   // 사이즈가 초과시 lru 인 원소를 제거한다.
                while (true) {
                    pair<int, int> pairKT = dq.back();
                    dq.pop_back();
                    // tag 가 갱신 시간이며 갱신시간이 유효한 것을 발견하면 종료함.
                    if (tagMap[pairKT.first] == pairKT.second + 1) {
                        my.erase(pairKT.first);
                        break;
                    }
                }
            }
        }
    }
};

 

D 풀이

deque 와 map 을 사용

class LRUCache {
public:
	LRUCache(int capacity) {
		this->capacity = capacity;
	}

	int get(int key) {
		if (m.count(key)) {
			// 순서 업데이트 해줘야함
			deque<pair<int,int>>::iterator it;
			int data = 0;
			for (it = dq.begin(); it != dq.end(); it++) {
				if (it->first == key) {
					data = it->second;
					dq.erase(it);
					break;
				}
			}
			dq.push_front(make_pair(key, data));
			return data;
		}
		return -1;
	}

	void put(int key, int value) {

		bool hasKey = m.count(key);
		if (hasKey) {
			// 중복되는 경우에 대한 처리 -> 이경우에는 key 를 최상단으로 업데이트 해줘야 한다.
			deque<pair<int, int>>::iterator it;
			for (it = dq.begin(); it != dq.end(); it++) {
				if (it->first == key) {
					dq.erase(it);
					break;
				}
			}
			dq.push_front(make_pair(key, value));
		}
		else {
			const int size = m.size();
			if (size == 0) {
				m[key] = value;
				dq.push_front(make_pair(key,value));
				return;
			}
			else if (size + 1 > capacity) {
				// capacity 가 넘어갈때 처리
				m[key] = value;
				// 마지막 원소 삭제후 삽입
				int lastKey = dq[size - 1].first;
				m.erase(lastKey);
				
				deque<pair<int, int>>::iterator it;
				for (it = dq.begin(); it != dq.end(); it++) {
					if (it->first == lastKey) {
						dq.erase(it);
						break;
					}
				}
				dq.push_front(make_pair(key, value));
			}
			else {
				m[key] = value;
				dq.push_front(make_pair(key, value));
			}
		}


	}

	deque<pair<int, int>> dq;
	unordered_map<int, int> m;
	int capacity;
};

 

W 풀이

vector 와 map 을 사용

#include <iostream>
#include <string.h>
#include <map>
#include <vector>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : vec_(capacity + 2) {
        capacity_ = capacity;
        size_ = 0;
    }

    void update(int key) {
        int i = 0;
        for (; i < size_; ++i) {
            if (vec_[i] == key)
                break;
        }

        for (; i < size_; ++i) {
            vec_[i] = vec_[i + 1];
        }
        vec_[size_ - 1] = key;
    }

    int get(int key) {
        if (cache_[key]) {
            update(key);
            return cache_[key];
        }

        return -1;
    }

    void put(int key, int value) {
        if (cache_[key]) {
            cache_[key] = value;

            update(key);
            return;
        }

        cache_[key] = value;
        vec_[size_] = key;

        ++size_;

        if (size_ > capacity_) {
            size_ = capacity_;
            int old = vec_[0];
            cache_[old] = 0;

            for (int i = 0; i < capacity_; ++i) {
                vec_[i] = vec_[i + 1];
            }

            //memcpy(&vec_[0], &vec_[1], (capacity_ - 1) * sizeof(int));
            vec_[capacity_ - 1] = key;
        }

        return;
    }

private:
    int capacity_;
    int size_;
    map<int, int> cache_;
    vector<int> vec_;
};

 

Z 풀이

list 와 unorded_map 을 사용

class LRUCache {
   struct CacheItem
   {
      list<int>::iterator iter;
      int value;
   };

public:
   LRUCache(int capacity) {
      //m_itemList.resize(capacity);
      nCapacity = capacity;
   }

   int get(int key)
   {
      unordered_map<int, CacheItem>::iterator iter = m_ItemMap.find(key);
      if (iter == m_ItemMap.end())
         return -1;
      else
      {
         m_itemList.erase(iter->second.iter);
         m_itemList.push_front(key);

         iter->second.iter = m_itemList.begin();
         return iter->second.value;
      }
   }

   void put(int key, int value) 
   {
      unordered_map<int, CacheItem>::iterator iter = m_ItemMap.find(key);
      if (m_itemList.size() != 0 && iter != m_ItemMap.end())
      {
         m_itemList.erase(iter->second.iter);
         m_itemList.push_front(key);
         iter->second.iter = m_itemList.begin();
         iter->second.value = value;
         return;
      }
      else if (m_itemList.size() == nCapacity)
      {
         list<int>::iterator last = m_itemList.end();
         --last;
         m_ItemMap.erase(*last);
         m_itemList.erase(last);
                  
      }

      m_itemList.push_front(key);
      CacheItem item = { m_itemList.begin() ,value };
      m_ItemMap[key] = item;
   }

private:
   list<int> m_itemList;
   unordered_map<int, CacheItem> m_ItemMap;
   int nCapacity;
};

 

O 풀이

unorded_map 과 list 사용

class LRUCache {
private:
   unordered_map<int, list<pair<int, int>>::iterator> oUmap;
   list<pair<int, int>> oListCache;
   int m_capacity;
public:
   LRUCache(int capacity) {
      m_capacity = capacity;
   }

   int get(int key) {
      auto iterUmap = oUmap.find(key);
      if (iterUmap == oUmap.end()) //못 찾으면
         return -1;

      auto oPair = *(iterUmap->second);
      oListCache.erase(iterUmap->second);//LRU 갱신 위해 제거
      oListCache.push_back(oPair);//캐시 추가
      oUmap[key] = --oListCache.end();//캐시 위치 저장

      return oPair.second;
   }

   void put(int key, int value) {
      auto iterUmap = oUmap.find(key);
      if (iterUmap != oUmap.end()) //찾으면
         oListCache.erase(iterUmap->second);//LRU 갱신 위해 제거
      else if( m_capacity == oListCache.size() ) //못 찾았는데 사이즈 Full이면
      {
         auto oPair = oListCache.front();
         oListCache.pop_front();
         oUmap.erase(oPair.first);
      }

      oListCache.push_back(make_pair(key, value));//캐시 추가
      oUmap[key] = --oListCache.end();//캐시 위치 저장
   }
};