문제

풀이

이 문제는 queue를 이용하여 풀 수 있다.
queue에 해당하는 값이 없는데 queue의 길이가 캐시 크기와 동일할 경우에는 첫 번째 들어간 값을 제거해준다. 그 후에 해당하는 값을 queue에 추가해준다. 이는 cache miss로 처리한다.
queue에 해당하는 값이 존재할 경우에는 처음 값을 제거하고 마지막에 다시 넣는다. 그리고 이는 cache hit로 처리한다.

코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> cache = new LinkedList<>();
        
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        for (int i = 0; i < cities.length; i ++) {
            String city = cities[i].toLowerCase();
            
            if (cache.contains(city)) {
                cache.remove(city);
                cache.offer(city);
                answer += 1;
            }
            else {
                if (cache.size() == cacheSize) {
                    cache.poll();
                }
                cache.offer(city);
                answer += 5;
            }
            
        }
        
        return answer;
    }
}

결과