프로그래머스: 캐시

문제

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

---

코드

private static final int MISS_RUN_TIME = 5;
public int solution(int cacheSize, String[] cities) {
    if (cacheSize == 0) {
        return cities.length * MISS_RUN_TIME;
    }

    Map<String, Integer> lru = new LinkedHashMap<String, Integer>(cacheSize, 1, true){
        @Override
        public boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
            return size() > cacheSize;
        }
    };

    int answer = 0;
    for(String key : cities) {
        key = key.toLowerCase();

        if(lru.containsKey(key)) {
            lru.get(key);
            answer += 1;
        } else {
            lru.put(key, 0);
            answer += MISS_RUN_TIME;
        }
    }

    return answer;
}

---

흐름

1. 캐시가 0인 경우엔 캐시에 저장 할 수 없으니 항상 miss 이므로 배열의 크기 만큼 5를 곱해서 return 한다.
2. LinkedHashMap의 경우 accessOrder parameter를 통해 Map의 순서를 access 기준으로 변경 할 수 있는데 우리는 LRU, 즉 가장 오래 사용되지 않은 데이터를 삭제 해야하므로 accessOrder를 true로 갖는 생성자로 LinkedHashMap 인스턴스를 생성한다.
3. 그 후 removeEldestEntry()를 override해서 캐시의 크기보다 Map의 사이즈가 커질 경우 가장 오래 사용되지 않은 데이터를 삭제하도록 수정한다.
4. 배열에서 문자열을 가져오면서 Map에 저장되어 있는지 비교한다.
5. Map에 저장되어 있다면, get()을 통해 access하고 1초를 더한다.
6. 저장되어 있지 않다면, put 하는데 이 때 Map의 크기가 캐시보다 크다면 아까 Override 한 removeEldestEntry()에 의해 가장 오래 사용되지 않은 값이 삭제되면서 지금 put한 데이터가 추가한다.
7. 캐시에 없는 데이터를 추가했으니 5초를 더한다.
8. 모든 초를 더한 값을 return 한다.

---

결과

번호	속도
테스트 1	통과 (1.11ms, 52.1MB)
테스트 2	통과 (1.20ms, 52.2MB)
테스트 3	통과 (1.08ms, 50.9MB)
테스트 4	통과 (1.23ms, 51.7MB)
테스트 5	통과 (0.94ms, 52.4MB)
테스트 6	통과 (0.78ms, 50.2MB)
테스트 7	통과 (0.78ms, 52.2MB)
테스트 8	통과 (1.12ms, 52.7MB)
테스트 9	통과 (1.15ms, 50.8MB)
테스트 10	통과 (1.34ms, 52.4MB)
테스트 11	통과 (45.53ms, 89.6MB)
테스트 12	통과 (1.45ms, 52.5MB)
테스트 13	통과 (1.43ms, 52.5MB)
테스트 14	통과 (1.69ms, 52.7MB)
테스트 15	통과 (2.42ms, 50.5MB)
테스트 16	통과 (2.85ms, 52.9MB)
테스트 17	통과 (0.78ms, 52MB)
테스트 18	통과 (4.34ms, 53.5MB)
테스트 19	통과 (4.28ms, 53.3MB)
테스트 20	통과 (4.15ms, 50.9MB)

---

테스트 케이스

assertEquals(42, test.solution(3, new String[]{"Jeju", "Pangyo", "Jeju", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
assertEquals(50, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
assertEquals(21, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}));
assertEquals(60, test.solution(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
assertEquals(52, test.solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
assertEquals(16, test.solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}));
assertEquals(25, test.solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
assertEquals(18, test.solution(1, new String[]{"LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA"}));

---

참고 사이트

• https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html