Leetcode 146) LRU Cache
in Algorithms
내 풀이
- LinkedHashMap 사용했다.. 성능 쓰레기임. Hashmap은 순서가 딱히 없고, LinkedHashMap은 들어온 순서가 있다.
- 아무래도 이 문제의 의도는 LinkedHashMap을 쓰는건 아니었던듯 싶다…
- 다시 풀기. 이번엔 Doubly Linkedlist로
class LRUCache {
int cnt=0;
Map<Integer,Integer> source = new LinkedHashMap<>();
public LRUCache(int capacity) {
cnt=capacity;
}
public int get(int key) {
int i=0;
if(source.get(key)!=null){
int val=source.get(key);
source.remove(key);
source.put(key,val);
return val;}
return -1;
}
public void put(int key, int value) {
if(source.get(key)!=null){
source.remove(key);
source.put(key,value);
return;
}
if(cnt==0){
int a = source.keySet().stream().findFirst().get();
System.out.println(a);
System.out.println(key);
source.remove(a);
cnt++;
}
source.put(key,value);
cnt--;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
double linked list로 다시 풀어봄
class LRUCache { class Node { int key; int val; Node(int key,int val){ this.key = key; this.val = val; } Node(){} Node next = null; Node prev = null; } int capacity; Map<Integer, Node> cache; Node head;Node tail; public LRUCache(int capacity) { this.capacity=capacity; //key와 노드 cache = new HashMap<>(); head = new Node(); tail = new Node(); head.next= tail; tail.prev=head; } public int get(int key){ if(cache.containsKey(key)){ moveBack(cache.get(key)); return cache.get(key).val; }else{ return -1; } } public void put(int key, int value) { if(cache.containsKey(key)){ cache.get(key).val =value; moveBack(cache.get(key)); }else{ if(capacity<=cache.size()){ // System.out.println("remove what? " + head.next.key); cache.remove(head.next.key); head.next=head.next.next; head.next.prev=head; } Node a = new Node(key, value); tail.prev.next= a; a.prev=tail.prev; tail.prev=a; a.next=tail; cache.put(key, a); } } public void moveBack(Node cur){ // System.out.println("move what? " + cur.key); cur.prev.next =cur.next; cur.next.prev=cur.prev; tail.prev.next=cur; cur.prev=tail.prev; tail.prev=cur; cur.next=tail; // System.out.println("head? " + head.next.key); // System.out.println("tail? " + tail.prev.key); } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
다른 답안
class LRUCache {
class Node{
int value;
int key;
Node next = null;
Node prev = null;
Node(int v, int k){
value = v;
key = k;
}
}
Node head = null, tail = null;
HashMap<Integer, Node> map = new HashMap<>();
int capacity = 0;
int size = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
Node n = map.get(key);
moveNodeToFront(n);
return n.value;
}
private void moveNodeToFront(Node n){
if(n == head)
return;
if(n == tail){
n.prev.next = null;
tail = n.prev;
n.next = head;
head.prev = n;
n.prev = null;
head = n;
}else{
n.prev.next = n.next;
n.next.prev = n.prev;
n.next = head;
head.prev = n;
n.prev = null;
head = n;
}
}
public void put(int key, int value) {
if(map.containsKey(key)){
Node n = map.get(key);
n.value = value;
moveNodeToFront(n);
return;
}
if(size == capacity){
size--;
map.remove(tail.key);
if(tail == head){
tail = head = null;
}else{
tail = tail.prev;
tail.next = null;
}
}
Node n = new Node(value, key);
map.put(key, n);
size++;
if(head == null){
head = tail = n;
}else{
n.next = head;
head.prev = n;
head = n;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
오답노트
head랑 tail을 dummy로 해서 위치를 지켜주면 exception 신경쓸게준다…!!
- 원소가 하나일때, 다 사라졌을 때 등등 이럴때 if문으로 head tail 다시 설정 안해줘도 되니까 생각해야하는 경우의 수가 줄어든다.
//이렇게 head인 노드를 직접 가리키기보다는 Node head; Node tail; //head,tail을 할당하고 head.next에 진짜 head를 넣는다. Node head= new Node(); Node tail = new Node();………. 흠.. 푸느라 ㅈㄴ 오래걸렸다. 링크 하나를 안했는데 모르고 있었음. 양방향인지 확인 안한 내 잘못…
class LRUCache {
class Node{
int key;int value;
Node next=null;
Node prev =null;
Node(){
}
Node(int k, int v){
key=k;value=v;
}
}
int max;
Node head = new Node();
Node tail = new Node();
Map<Integer,Node> m = new HashMap<>();
public LRUCache(int capacity) {
max=capacity;
head.next= tail;
tail.prev= head;
}
public int get(int key){
if(m.containsKey(key)){
changePosition(m.get(key));
return m.get(key).value;
}
return -1;
}
public void changePosition(Node cur){
Node a = cur.prev;
Node b= cur.next;
a.next=b;
b.prev = a;
cur.prev= tail.prev;
tail.prev.next=cur;
cur.next=tail;
tail.prev=cur;
}
public void put(int key, int value) {
if(!m.containsKey(key)){
if(max==m.size()){
Node old = head.next;
head.next=old.next;
old.next.prev=head;
m.remove(old.key);
}
Node newNode= new Node(key,value);
m.put(key,newNode);
tail.prev.next=newNode;
newNode.prev=tail.prev;
newNode.next=tail;
tail.prev=newNode;
}else{
//key 이미 있는 경우
changePosition(m.get(key));
m.get(key).value= value;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
