[프로그래머스][JAVA][Lv. 2] 캐시

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        Queue<String> cache = new LinkedList<>();
        int answer = 0;
        
        for (int i = 0; i < cities.length; i++) {
            String lowerCity = cities[i].toLowerCase();
            
            if (cacheSize == 0) answer += 5; // 캐시 사이즈가 0일 때
            else {
                if(!cache.contains(lowerCity)) {  // cache miss
                    if (cache.size() == cacheSize) cache.poll();
                    cache.add(lowerCity);
                    answer += 5;
                }
                else {  // cache hit
                    Queue<String> newCache = new LinkedList<>();
                    
                    int count = (cache.size() == cacheSize ? cacheSize : cache.size());
                    for (int j = 0; j < count; j++) {
                        String city = cache.poll();
                        if (!city.equals(lowerCity)) newCache.add(city);
                    }
                    newCache.add(lowerCity);
                    cache = newCache;
                    answer++;
                }
            }
        }
        return answer;
    }
}

---

후기

그냥 캐시 크기만큼 저장한 후에 LRU 조건에 따라서 캐시에 있는 것 중에서 가장 오래된 것을 꺼내 새로운 것과 교환해주면 된다. 관건은 어떤 조건에서 어떤 행동을 하느냐인데 캐시 사이즈가 0일 때는 무조건 새로 추가하는 것 취급을 하고, 캐시 미스일 때는 큐 사이즈가 캐시 크기보다 작으면 새로운 것만 넣어주고, 큐 사이즈가 캐시 크기와 같으면 최대 크기 유지를 위해서 추가와 동시에 제일 오래된 것을 빼주어야 한다. 큐를 이용했기 때문에 특정 조작 없이 제일 처음에 들어간 것을 poll() 메서드를 이용해서 빼주기만 하면 된다. 그 다음은 캐시 히트일 경우이다. 히트일 경우는 큐의 크기가 최대일 때나 아닐 때 동일하게 순서를 변경해주어야 한다. 나는 큐를 오래된 순서대로 빼면서 새로 들어와야하는 값은 제외한다. 그리고 마지막에 새로 들어와야하는 값을 추가하는 식으로 풀었다.