LeetCode - LRU Cache java 문제풀이

내가 이런 구현에 재능이 없었다.

참 오래 공부를 안했다.

강의를 대충 보고 풀었는데도 1시간 정도 소요되었다.

 

문제를 보고 풀이를 할 때 좀 더 확실히 보고 풀어야겠다는 생각이 든다.

 

import java.util.*;

// 이중 LinkedList 를 구현할 Class
class CacheItem {
    CacheItem prev;
    CacheItem next;
    int key;
    int value;
    public CacheItem(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {
    // 맨 앞, 맨 뒤에 접근해야 한다.
        //  Double Linked List -> 본인 앞뒤를 보는 클래스로 만들자
    // O(1) 으로 접근
        // HashMap
    // capacity


    int capacity;
    Map<Integer, CacheItem> map;
	// head 랑 tail 로 삭제할 대상을 확정지어야 한다.
	CacheItem head;
    CacheItem tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
    }
    
    public int get(int key) {
        // 없으면 return -1;
        if (!map.containsKey(key)) {
            return -1;
            // 이건 쉽다. 값이 없으면 -1 돌려주기
        } else {
            // 값이 있으면 구하면 된다.
            // 어떤 식으로 동작할지 생각해 보자
            	// 값을 돌려준다.
                // 그리고 원래 있었던 값이면 거기서 빼서 맨앞으로 보낸다.
                // 맨뒤에 있었다면 그 앞에 애가 맨뒤가 되어야 한다.
            CacheItem curr = map.get(key);
            
            if(head == curr) {
				// 원래부터 맨앞이면 건드릴게 없이 돌려주면 된다.
            } else {
                // 맨 뒤에 있다면?
                if(tail == curr) {
                	// 원래 맨앞에 있던애는 지금애 뒤로 가고
                    head.prev = curr;
                    curr.next = head;
                    // 지금애가 맨앞으로 간다.
                    head = curr;
                    // 맨 뒤 값은 원래 값이 있던애의 앞
                    tail = tail.prev;
                    tail.next = null;
                    head.prev = null; // head, tail 은 이전 앞/뒤와의 관계 끊기
                } else {
                    // 중간에 있었다면?
                    // AS-IS : head - head.next - ... - curr.prev - curr - curr.next 
                    // TO-BE : curr - head - head.next - ... curr.prev - curr.next
                    curr.prev.next = curr.next;
                    curr.next.prev = curr.prev;
                    
                    // 나머지는 똑같이
                    head.prev = curr;
                    curr.next = head;
                    curr.prev = null;
                    head = curr;
                }
            }
                
            return curr.value;
        }
    }
    
    public void put(int key, int value) {
    	// put 은 처음에 고민을 많이 했는데, 어차피 get 할때 넣는거 다 해주니까 얘는 없는 경우 세팅만 해주면 된다.
        CacheItem curr = map.get(key);

        // 이미 있는 경우 변경
        if(curr != null) {
            curr.value = value;
            get(key);
        } else {
        	// 원래 없었다면 새로운 값을 넣어준다.
            curr = new CacheItem(key, value);
            
            // 텅 빈 상태라면 이게 처음이자 마지막
            if (map.size() == 0) {
                head = curr;
                tail = curr;
            } else {
                // 이미 뭐가 있으면 적용    
                curr.next = head;
                head.prev = curr;
                head = curr;
            }

            map.put(key, curr);
        }

		// 크기 넘어가면 기존거 제거
        if(capacity < map.size()) {
            map.remove(tail.key);
            tail = tail.prev;
            tail.next = null;
        }
    }
}

/**
 * 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);
 */