캐시

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

프로그래머스

 

LRU 알고리즘에 대해 간략하게 나마 알아야 한다.

 

캐시 사이즈를 초과하게 되는 경우 가장 적게 hit된 항목을 먼저 날려야 한다는 정도만 알아도 될듯.

 

그래서 Queue를 사용했는데, 빠른 탐색을 위해 캐시를 위한 캐시인 HashSet을 추가로 사용했다.

 

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        
        if (cacheSize == 0) return cities.length * 5;
        
        Set<String> temp = new LinkedHashSet();
        Queue<String> cache = new LinkedList();
        
        int answer = 0;
        for (String city : cities) {
            
            city = city.toLowerCase();
            
            if (temp.contains(city)) {
                cache.remove(city);
                cache.offer(city);
                answer++;
            } else {
                if (!cache.isEmpty() && cache.size() == cacheSize) {
                    String last = cache.poll();
                    temp.remove(last);
                }
                cache.offer(city);
                temp.add(city);
                answer += 5;
            }
            
        }
        
        return answer;
    }
}