캐시

Posted on Edited on In , ,

문제정의

캐시의 용량과 도시이름이 주어질 때, LRU 캐시 알고리즘을 사용할 때, 총 반응 시간을 계산하는 코드이다. 도시 이름은 대소문자를 가리지 않는다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package level2;
import java.util.LinkedHashMap;
import java.util.Map;

public class Cache {

    //프로그래머스 문제풀이 Level2 캐시

    public static void main(String[] args) {
        int answer = 0;
        int cacheSize = 3;
        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
        Map<String, Integer> map = new LinkedHashMap<>(cacheSize, 0.75f, true);
        if(cacheSize == 0)
            answer = cities.length*5;
        else
        {
            for(String s : cities)
            {
                s = s.toLowerCase();
                //맵에 없는 경우
                if(map.getOrDefault(s, 0) == 0)
                {
                    if(map.size() == cacheSize)
                    {
                        Map.Entry leastUsedEntry = map.entrySet().iterator().next();
                        String key = (String)leastUsedEntry.getKey();
                        map.remove(key);
                    }
                    map.put(s, 1);
                    answer += 5;

                }
                else
                    answer++;   
            }
        }
        
        System.out.println(answer);
    }
    
}
자바는 정말 놀라운 언어이다. 호출 빈도에 따라서 정렬해주는 맵이 이미 존재했다! LinkedHashMap에서 호출 빈도에 따른 정렬을 제공하는데, 평소에는 false로 되어있다. 이를 true로 바꿔주면 LRU를 구현하기 한 층 쉬워진다.

일단 캐시 사이즈가 0인 경우를 따로 처리한다. 0인 경우 맵의 크기가 0이 되어 예외가 발생하기 때문이다. 0인 경우에는 모든 도시에서 cache miss가 발생하므로 전체 크기에 5를 곱한 값을 반환한다. 그렇지 않은 경우 캐시를 활용한다. 만약 들어온 도시 이름이 맵에 없는 경우 두 가지 경우로 나뉜다.

  1. 캐시가 이미 다 차서 오래된 것을 제거해야 하는 경우
  2. 캐시에 아직 여유 공간이 있는 경우

1번의 경우 맵에서 호출된지 가장 오래된 원소를 지워야한다. 이는 map에서 첫번째 원소를 제거하면 되므로 iterator의 첫번째 키값을 받아 제거한다. 이 뒤에 원소를 추가한다. 이 과정을 거치고 정답에 5를 더해준다.

만약 캐시에 도시 이름이 있을 경우 반응시간을 1늘려주면 된다.

호출 시간에 따른 정렬은 시간복잡도가 정확히 나타나있지 않다. 다만 \(logn\)으로 추측이 간다(이진 탐색을 활용할 가능성이 높다). 따라서 최종시간복잡도는 \(O(nlogn)\)이다.

테스트



자바 기본라이브러리를 잘 익혀야겠다.