티스토리 뷰
728x90
반응형
문제 요약
- 알고리즘 분류: Hash, 자료구조, 링크드 리스트
- 난이도: Medium
- 문제내용:
- LRU Cache class 구현해라
- LRUCache(int capacity) capacity은 용량 사이즈이다.
- get 메소드는 key가 있을경우 값을 출력하고 아닐경우 -1로 출력한다.
- put 메소드는 값을 집어 넣는다. 용량이 초과 할경우 최근 사용도 순으로 삭제한다.
- 사이트 주소: https://leetcode.com/problems/lru-cache/description/
문제풀이
이번 문제는 자료구조 구현이다. 생성자, 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));
}
}
728x90
반응형
'알고리즘 > Leetcode' 카테고리의 다른 글
[Leetcode] 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers (1) | 2024.03.21 |
---|---|
[Leetcode] 1631. Path With Minimum Effort (0) | 2024.03.15 |
[Leetcode] 131. Palindrome Partitioning (0) | 2024.03.13 |
[Leetcode] 343. Integer Break (0) | 2024.03.09 |
[Leetcode] 1. Two Sum (0) | 2024.03.05 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 배열
- 조합
- 백준
- 이론
- 누적합
- 그리디
- 동적 계획법
- level2
- 수학
- Python
- DFS
- spring-boot
- java
- DP
- 재귀호출
- 문자열
- 동적계획법
- LeetCode
- 구현
- Programmerse
- 넓이 우선 탐색
- 그래프
- JSCODE
- 알고리즘
- Greedy
- BFS
- 백트레킹
- 파이썬
- 자바
- BaekJoon
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함