Today's Algorithm(2019-02-05)

programmers. 캐시

문제를 푸는 조건 중 하나인 LRU를 알면 크게 어렵지 않은 문제입니다. LRU는 사실 운영체제에서 나오는 개념인데요. 이에 대해서 간략하게 설명드려볼게요.

음.. 컴퓨터 내 처리 작업에서 가장 시간 많이 사용하는 작업이 입출력 작업입니다. 그렇기 때문에 그 시간을 줄이고자 데이터를 처리하는 곳과 데이터가 저장된 곳 사이에 캐시라는 저장소를 두어 자주 사용되는 데이터들을 저장해둡니다. 하지만 캐시라는 저장소는 유한한 공간이 아니기 때문에(만약 중간에 있다고 공간을 늘려버리면 결국 데이터가 저장된 곳과 같은 곳이 되어버릴 것입니다) 어떠한 규칙에 의해 새로 보관되는 데이터, 버려지는 데이터가 구분되어야 할 것입니다. LRU는 그러한 규칙 중 하나로 Least Recently Used의 약자입니다. 한 마디로 말하자면 '가장 오래된 것'이 버려지는 데이터의 대상이 되는 것입니다.

 

처음에 이 문제를 풀 때 가장 오래되는 것이지만 그 중에서도 hit 수에 따라 분류를 해야하는 줄 알았습니다. 그렇게 되면 hit수, index(오래된 순인지 알기위함)이 정렬의 기준이 되어야했습니다. 그렇지만 단순하게 오래된 순만 정렬하면 되더라구요. 그렇기 때문에 문제를 단순하게 풀 수 있었습니다. 이럴 땐 Queue가 적절하게 사용될 수 있죠. 하지만 기본적인 Queue는 해당 순서에 찾아갈 수 없고 앞에서 부터 없애야합니다. 하지만 기존에 있는 City의 경우 가장 오래된 것이라는 것을 구분하기 위해 삭제하고 다시 Queue에 넣어줘야 했기 때문에(그렇게 되면 가장 최근에 사용된 것이라고 알 수 있겠죠) LinkedList 구현체를 사용하였습니다.

 

주의할 점은 캐시가 0일때도 있다는 점입니다. 이를 처음에 생각하지 못해 좀 찾았었는데요. 쉽게 찾아지지 않더라구요. 제가 그렇지 않은 테스트 케이스를 만들지 못해서. 그런 경우는 아래와 같은 테스트일 것입니다.

@Test
    public void test6_2() {
        int cacheSize = 0;
        String[] cities = {"Jeju", "Jeju", "Jeju", "Jeju", "Jeju", "Jeju"};
        assertThat(problem.solution(cacheSize, cities)).isEqualTo(30);

같은 이름의 도시가 있지만 캐시가 0이기 때문에 결국 매번 miss가 될 수 밖에 없는 경우이죠.

 

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        LinkedList<String> queue = new LinkedList<>();

        for (int i = 0; i < cities.length; i++) {
            String tempCity = cities[i].toLowerCase();
            if (queue.contains(tempCity)) {
                String theCity = queue.remove(queue.indexOf(tempCity));
                queue.offerLast(theCity);
                answer++;
                continue;
            }

            if(queue.size() >= cacheSize) queue.pollFirst();
            if(cacheSize > 0) queue.offerLast(tempCity);
            answer += 5;
        }

        return answer;
    }
}