[JAVA] 캐시 - LinkedList

캐시는 데이터를 보관하는 임시 저장소입니다.

https://programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

 

생각과정

- LRU 알고리즘은 오랫동안 사용하지 않는 것부터 삭제해 메모리 효율을 높인다. => Queue 활용

- cache hit일 경우, 해당 cache 데이터를 queue 맨 뒤로 보낸다.

- cache miss일 경우, queue의 맨 앞 데이터를 삭제하고 새로운 데이터를 추가한다.

- 영어 대소문자 구분이 없으므로 소문자로 통일하여 비교한다.

 

구현

import java.util.LinkedList;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>(); //Queue
        
        for(int i=0; i<cities.length;i++){
            //캐시에 있는지 확인 - 소문자로 통일해서 비교
            String city = cities[i].toLowerCase();
            int index = cache.indexOf(city);
            if(index != -1){
                //cache hit!
                answer += 1;
                //hit한 데이터는 큐의 맨 뒤로 이동시킴
                cache.remove(index);
                cache.add(city);
            }
            else{
                //cache miss!
                answer += 5;

                //캐시에 집어넣기
                if(cacheSize != 0){
                    cache.add(city);
                }
                //캐시 길이 검사 후 초과하면 제일 오래된 데이터 삭제
                if(cache.size() > cacheSize){
                    cache.removeFirst();
                }
            }
        }
        
        return answer;
    }
}

 

결과

다른 문제보다 코드길이가 훨씬 짧았다.

LinkedList

- 자바에서 Queue를 구현할 때 많이 사용하는 자료구조이다. Queue 인터페이스를 구현했다.

- 값 추가

list.add(value); //데이터를 queue 맨 뒤에 붙인다

- 값 삭제

list.remove(index);

list.removeFirst(); //첫번째 인덱스값 삭제

list.removeLast(); //마지막 인덱스값 삭제

- 값 탐색

list.contain(value); //값이 있으면 true 반환

list.indexOf(value); //값이 있으면 해당 index 반환, 없으면 -1 반환

- 크기

list.size();

 

LRU(Least Recently Used) 알고리즘

- 페이지 교체 알고리즘 중 하나로, 한정된 자원(메모리 공간)을 효율적으로 사용하기 위해 만들어졌다.

- 오랫동안 사용하지 않은 데이터는 앞으로 사용할 확률이 적은 것으로 간주되어 제거될 우선순위가 높다.

- 구현방법은 2가지로, 마지막 사용 시간와 LinkedList를 사용하는 방법이 있다.

- 마지막 사용 시간 방법

데이터를 저장할 때 마지막 사용 시간을 함께 저장해두고, 데이터를 사용할 때 시간을 갱신한다. 메모리 공간이 가득 차면 마지막 사용시간이 제일 오래된 데이터부터 삭제한다.

=> 단점: 삭제할 때 시간이 오래 걸리고, 시간 데이터를 저장할 추가 메모리를 요구한다.

- LinkedList 방법

Queue를 활용해 메모리 공간이 가득 찰 경우 맨 앞에 있는 데이터부터 삭제한다.

=> LinkedList가 더 효율적인 것 같다.

 

참고

https://coding-factory.tistory.com/552

[Java] 자바 LinkedList 사용법 & 예제 총정리

https://gomguard.tistory.com/115

페이지 교체 알고리즘 - LRU