[프로그래머스] 1차 캐시 Java

1차 캐시

문제에서 LRU 알고리즘을 사용하라고 알려줍니다.

LRU 알고리즘이란 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법입니다.

그러므로, LinkedList 에서 배열의 수를 유지하며 값이 히트하면 지우고 제일 앞으로 값을 가져오고 값이 미스라면 첫번째에 넣는 방식입니다.

하지만 LinkedList 는 remove 시간 복잡도가 O(n)이므로 다른 방법을 사용하면 시간을 더 줄일 수 있습니다.

import java.util.LinkedList;

public class Solution {
    static final int hit = 1;
    static final int miss = 5;

    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) return miss * cities.length;//0이면 hit 못시켜서 다 miss로 처리

        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();

        for (int i = 0; i < cities.length; i++) {
            String city = cities[i].toLowerCase();//예제 중 대소문자 다른거 판별

            if (cache.remove(city)) {//배열에 값이 존재하면 true 반환하고 지우기
                cache.addFirst(city);//첫번째로 이동
                answer += hit;
            } else {
                if (cache.size() == cacheSize) cache.pollLast();//배열 숫자 유지시키기
                cache.addFirst(city);//첫번째 넣기(값이 존재 안하니깐)
                answer += miss;
            }
        }
        return answer;
    }
}