Gidhub BE Developer

[Programmers] 캐시

2021-01-30
goodGid

캐시

Problem

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.
캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

Example


[1] Code (21. 01. 30)

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) { // [1]
            return cities.length * 5;
        }
        
        int answer = 0;

        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();
        }

        for (int i = 0; i < cities.length; i++) {
            String key = cities[i];

            // Cache에 존재한다.
            if (map.containsKey(key)) {
                answer += 1;
                updateValues(map, key);
                map.computeIfPresent(key, (k, v) -> 1); // 해당 값 1로 초기화
                continue;
            }

            // Cache에 값이 없지만 넣을 순 있다.
            if (map.size() < cacheSize) {
                answer += 5;
                updateValues(map, key);
                map.put(key, 1);
                continue;
            }

            // Cache에 값이 없고 넣을 수도 없다.
            answer += 5;
            String maxKey = "";
            Integer maxValue = 0;
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                String entryKey = entry.getKey();
                map.computeIfPresent(entryKey, (k, v) -> v + 1);
                if (maxValue < entry.getValue()) {
                    maxKey = entryKey;
                    maxValue = entry.getValue();
                }
            }
            map.remove(maxKey); // 오래된 값 지우기
            map.put(key, 1); // 새로운 값 넣기
        }
        return answer;
    }

    private void updateValues(HashMap<String, Integer> map, String key) {
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String entryKey = entry.getKey();
            if (entryKey == key) {
                continue;
            }
            map.computeIfPresent(entryKey, (k, v) -> v + 1);
        }
    }
}
  • [1] : cacheSize가 0인 경우를 예외처리해주지 않으면

    Cache에 값이 없고 넣을 수도 없는 경우 추가로 예외 코드가 들어가야 한다.

    cacheSize가 0인 경우 map에 put 하면 안 되기 때문이다.

    map.put(key, 1); // 새로운 값 넣기


Reference


Comments

Index