Lv 2. 1차 캐시

LRU 에 대한 개념이 있어야 한다. cache hit, cache miss 와 같이 이해할 수 없던 용어가 많아 LRU에 대해 공부하고 이해하여 풀 수 있었다.
가장 오랫동안 사용되지 않은 데이터는 캐시에서 제거하고 사용 된 적 있는 데이터는 캐시에 남겨 둠으로써 캐시메모리 관리하는 방법이다. 
다음은 풀이코드이다.

import java.util.*;

class Solution {
    LinkedList<String> list = new LinkedList<>();
    int answer = 0;
    public int solution(int cacheSize, String[] cities) {
        
        if(cacheSize==0)
            return cities.length*5;
        
        for(String str : cities){
            str = str.toLowerCase();
            if(list.contains(str)){
                answer+=1;
                list.remove(str);
                list.add(str);
            }else{
                if(list.size() == cacheSize ){
                    list.remove(0);
                }
                list.add(str);
                answer+=5;
            }
        }
        return answer;
    }
    
}

 

LinkedList를 사용한 이유는 ArrayList를 사용할 경우 중간 정보를 삭제해야 하기 때문에 시간복잡도 측면에서 손해를 보기 때문이고 toLowerCase와 contains, remove, add 등 여러 함수들을 써먹고 기억해 볼 수 있는 좋은 문제였다.

 

 

String
- toLowerCase()

LinkedList

- remove()
- size()

- add()

- contains()