146. LRU Cache

문제

int 타입의 key, value 가 들어오고 저장하고나서 capacity (용량)이 초과된 경우,

가장 오래 사용하지 않은 값을 제거하는 lru 캐시를 구현하는 문제다.

 

풀이 

이 문제는 LinkedHashMap 을 이용해서 풀수도 있고, 직접 linkedList 를 이용해서 풀 수도 있다.

 

코드

class LRUCacheMapClass {

        private Map<Integer, Integer> map;

        public LRUCacheMapClass(int capacity) {
            this.map = new LinkedHashMap(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > capacity;
                }
            };
        }

        public int get(int key) {
            return map.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            map.put(key, value);
        }
}

 

1. 기본적으로 LinkedHashMap 은 내부에 Node 를 구현하여 값이 들어온 순서대로 저장된다.

자바의 LinkedHashMap 생성자에는 accessOrder 라는 인자를 받을 수 있는데 true 로 설정하면,

get 호출한 키값의 순서를 가장 마지막으로 옮긴다.

 

2.  removeEldestEntry() 메소드를 오버라이드한다.

해당 메소드는 가장 오래된 원소를 제거할지 여부를 결정하는 메소드로 기본적으로 false 이다.

만약 단순히 true 로 변경하면 put 메소드 호출시마다 기존 원소를 제거하고 새로운 원소를 저장하게 된다.

참고로, 가장 오래된 원소는 맵의 첫번째에 저장된 원소이다.

 

단순히 true 가 아닌 특정 capacity 이상의 수일때만 동작하게하기 위해서는 size() > capacity 를 주면 된다.

 

3. get, put 은 따로 변경할것이 없다.

1번에서 get 호출된 키는 무조건 마지막 위치로 이동되고,

2번에서 put 호출되면 removeEldestEntry 에 의해 첫번째 원소가 삭제되기 때문에 추가적으로 작성할 코드는 없다.