[프로그래머스] 캐시 (JAVA)

입력 형식

캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

조건

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
cache hit일 경우 실행시간은 1이다.
cache miss일 경우 실행시간은 5이다.

Code

import java.util.*;
class Solution {
    private int cache_hit = 1;
    private int cache_miss = 5;
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        for(String city : cities) {
            city = city.toLowerCase();
            if(cache.contains(city) && cacheSize>0) {
                answer += cache_hit;
                cache.remove(city);
            } else {
                answer += cache_miss;
                if(cache.size()==cacheSize) {
                    cache.pollLast();
                }
            }
            cache.offerFirst(city);
        }
        return answer;
    }
}

Comment

LRU(Least Recently Used)
가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.
LFU(Least Frequently Used)
가장 적게 참조한 페이지를 캐시에서 교체하는 것이다.

LRU에 대한 내용을 알지 못했다. Cache 개념을 알게되어 좋은 문제였다.