프로그래머스 - 캐시

문제를 해결하기 전 알아야할 지식

캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 하기 때문에 '캐시 교체 알고리즘'을 사용한다.

LRU(Least Recently Used) : 직역하자면 '가장 최근에 사용된' 이란 뜻으로, 메모리에 남아있는 캐시 중 가장 오랫동안 사용되지 않은 캐시는 앞으로도 사용될 확률이 적다고 판단하여 새로운 캐시로 교체 한다는 알고리즘이다.
LRU를 구현하기 위해서는 n의 크기를 가지는 DoublyLinkedList(or Queue)와 이를 추적하기 위한 n의 크기를 가지는 HashMap이 필요하다.

Cache Hit : 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우

Cache Miss : 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우

---

나는 풀이를 위해 LinkedList를 사용하기로 하였다.

public class Test_24_Cache {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        List<String> cache = new LinkedList<>();

        // 캐시의 크기가 0일 경우 전부 cache miss
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        // 캐시의 크기가 0이 아닐 경우
        for (int i = 0; i < cities.length; i++) {
            // 도시 이름은 대소문자 구분이 없기 때문에
            String cityName = cities[i].toLowerCase();

            // cache hit일 경우
            if (cache.contains(cityName)) {
                // 도시 이름을 처음에서 마지막으로 교체
                cache.remove(cityName);
                cache.add(cityName);
                answer++;

            } else { // cache miss일 경우
                // 캐시의 용량이 다 찼을 경우
                if (cache.size() >= cacheSize) {
                    // 가장 앞에있는 요소가 오랫동안 사용하지 않았으므로
                    cache.remove(0);
                }

                cache.add(cityName);
                answer += 5;
            }
        }

        return answer;
    }
}

처음에 문제를 보고 당황하고 헤맸지만,
LRU에 대한 개념을 이해하고나니 생각보다 간단한 문제였고 캐시에 대한 개념을 다시 한 번 복습해 볼 수 있었다.