[Leetcode] 146. LRU Cache

문제 요약

• 알고리즘 분류: Hash, 자료구조, 링크드 리스트
• 난이도: Medium
• 문제내용:
  • LRU Cache class 구현해라
  • LRUCache(int capacity) capacity은 용량 사이즈이다.
  • get 메소드는 key가 있을경우 값을 출력하고 아닐경우 -1로 출력한다.
  • put 메소드는 값을 집어 넣는다. 용량이 초과 할경우 최근 사용도 순으로 삭제한다.
• 사이트 주소: https://leetcode.com/problems/lru-cache/description/

LRU Cache - LeetCode

문제풀이

 이번 문제는 자료구조 구현이다. 생성자, get, put 3개만 구현 하면 된다.

생성자

 용량 크기, key-value 자료구조를 만든다.

Python

- OrderedDict 사용하면 순서대로 저장해주는 모듈이다.

    def __init__(self, capacity: int):
        self.size = capacity
        self.cache = OrderedDict() # 순서대로 저장하는 자료구조

Java

- LinkedHashMap  순서대로 저장해주는 클래스이다.

public LRUCache(int capacity) {
    this.size = capacity;
    this.cache = new LinkedHashMap(); // 순서대로 저장 해주는 Map
}

 

Get

 key 위치를 맨뒤로 보낸다.

Python

.move_to_end(key, last=Ture): 최근 사용것을 맨 뒤로 보낸다. last = False 사용시 맨 앞으로 보낸다.

    def get(self, key: int) -> int:
        if key not in self.cache: return - 1
        # 사용후 맨뒤로 보낸다.
        self.cache.move_to_end(key)
        return self.cache[key]

Java

containsKey(key): Map안에 key가 존재하는지 확인한다.

public int get(int key) {
    	// 출력하고 맨 뒤로 보낸다.
    	if(cache.containsKey(key)) {
    		int value = cache.get(key);
    		cache.remove(key);
    		cache.put(key, value);
    		return value;
    	}
        return -1;
    }

 

Put

 key-value 값을 저장하고 사이즈 클 경우 최근에 사용하지 않는것을 지운다.

Python

popitem(last=False)

 - last= False : 맨앞에것을 삭제한다.

 - last= True :  맨 뒤에 것을 삭제한다.

    def put(self, key: int, value: int) -> None:
        self.cache[key] = value
        self.cache.move_to_end(key)
        print(self.cache)
        if len(self.cache.keys()) > self.size:
            self.cache.popitem(last=False)

Java

 keySet().iterator().next(): Map 맨 앞에 있는 것을 출력한다.

public void put(int key, int value) {
    // 캐시 안에 키값이 존재할경우 기존 키 삭제하고 다시 집어 넣음
    if(cache.containsKey(key)) {
        cache.remove(key);
    }
    cache.put(key, value);
    // 용량 초과일경우 최근것을 삭제한다.
    if(cache.size() > size) {
        // 최근 사용한 키 또는 저장한키를 추출함
        int removeKey = cache.keySet().iterator().next();
        cache.remove(removeKey);
    }
}

 

 특별하게 구현하는 쪽 고민 보다. OrderedDict , LinkedHashMap같은 Map과 순서가 관리되는 모듈만 사용하는 것 중점으로 공부하면 된다.

Code

Python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.size = capacity
        self.cache = OrderedDict() # 순서대로 저장하는 자료구조

    def get(self, key: int) -> int:
        if key not in self.cache: return - 1
        # 사용후 맨뒤로 보낸다.
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        self.cache[key] = value
        self.cache.move_to_end(key)
        print(self.cache)
        if len(self.cache.keys()) > self.size:
            self.cache.popitem(last=False)


lRUCache = LRUCache(2)
lRUCache.put(1, 1)
lRUCache.put(2, 2)
print(lRUCache.get(1))
lRUCache.put(3, 3)
print(lRUCache.get(2))
lRUCache.put(4, 4)
print(lRUCache.get(1))
print(lRUCache.get(3))
print(lRUCache.get(4))

Java

import java.io.IOException;
import java.util.LinkedHashMap;

class LRUCache {

	int size;
	LinkedHashMap<Integer, Integer> cache;
	
    public LRUCache(int capacity) {
        this.size = capacity;
        this.cache = new LinkedHashMap(); // 순서대로 저장 해주는 Map
    }
    
    public int get(int key) {
    	// 출력하고 맨 뒤로 보낸다.
    	if(cache.containsKey(key)) {
    		int value = cache.get(key);
    		cache.remove(key);
    		cache.put(key, value);
    		return value;
    	}
        return -1;
    }
    
    public void put(int key, int value) {
    	// 캐시 안에 키값이 존재할경우 기존 키 삭제하고 다시 집어 넣음
    	if(cache.containsKey(key)) {
    		cache.remove(key);
    	}
    	cache.put(key, value);
    	// 용량 초과일경우 최근것을 삭제한다.
    	if(cache.size() > size) {
    		// 맨앞에 key를 출력한다.
    		int removeKey = cache.keySet().iterator().next();
    		cache.remove(removeKey);
    	}
    	
    }
    
    public static void main(String[] args) throws IOException {
    	LRUCache lRUCache = new LRUCache(2);
    	lRUCache.put(1, 1); // cache is {1=1}
    	lRUCache.put(2, 2); // cache is {1=1, 2=2}
    	System.out.println(lRUCache.get(1));   // return 1
    	lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
    	System.out.println(lRUCache.get(2));    // returns -1 (not found)
    	lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
    	System.out.println(lRUCache.get(1));    // return -1 (not found)
    	System.out.println(lRUCache.get(3));    // return 3
    	System.out.println(lRUCache.get(4)); 
    }
}