캐시
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); // 새로운 값 넣기