문제 설명
오늘은 자바에서 제공하는 LinkedHashMap을 사용하여 프로그래머스의 Level2 난이도 문제, [1차] 캐시를 풀어보았습니다. 문제 보러가기
문제를 한 문장으로 요약하자면,
"LRU 캐시를 구현하여, 입력되는 데이터 참조 순서에 따른 '총 메모리 접근 시간'을 계산하는 문제입니다."
입력
- int cacheSize : 캐시의 크기를 의미. (0 <= cacheSize <= 30)
- String[] cities : 참조하고자 하는 도시 이름들이 저장된 배열 (<= 100,000)
조건
- 도시 이름은 영문자로만 구성, 대소문자의 구분이 없음
- 캐시 교체 알고리즘은 LRU(Least Recently Used) 사용
- Cache hit일 때, 실행 시간 1
- Cache miss일 때, 실행 시간 5
HashMap vs LinkedHashMap
공통점
- 각 entry들은 (key, value) 형태로 저장됩니다.
- Hashing을 사용하기 때문에 빠른 데이터 조회, 추가, 제거가 가능합니다.
- 중복되는 key값을 가진 데이터를 추가하면 기존의 있는 value가 갱신됩니다.
- 조회, 추가, 제거를 위해 get(), put(), remove()를 동일하게 사용합니다.
차이점 - 추가된 순서를 기억하는가?
- HashMap : (key, value)를 추가된 데이터들의 순서를 기억하고 있지 않습니다. 원하는 순서로 put을 하더라도, HashMap 내에서 다른 순서로 저장되게 됩니다.
- LinkedHashMap : 기본적으로, 데이터들이 사용(추가 or 조회)된 순서를 기억하고 있습니다. 각 데이터들이 사용된 순서를 알고 있기 때문에, 오래된 entry를 먼저 교체하는 LRU 알고리즘을 구현하는 데 적합합니다.
LinkedHashMap 생성하기
import java.util.Map;
import java.util.LinkedHashMap;먼저 위 두 가지 클래스를 import 해줍니다.
Map<String, String> cache = new LinkedHashMap<>(cacheSize, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > cacheSize;
}
};LinkedHashMap을 선언하는 부분입니다.
key는 도시 이름인 String 타입이고, value는 사용하지 않는 값이라 둘다 그냥 String 타입으로 지정하였습니다.
1. 생성자 매개변수
생성자에는 cacheSize, 0.75f, true 라는 3가지 인수를 넣어줬습니다.
LinkedHashMap의 총 5가지 생성자들 중 제가 사용한 생성자는 아래와 같습니다.
-
initialCapacity : 초기 capacity, 즉 LinkedHashMap의 bucket 갯수입니다. bucket은 element를 여러 곳에 분산시켜놓기 위해 사용하는 공간입니다. 예를 들어 10개의 bucket을 가진 HashMap에 100개의 element를 추가한다면, 한 bucket에 10개씩 element가 분산되는 것입니다. 클 수록 빠른 검색이 가능하지만 메모리 낭비가 생기고, 작아지면 그 반대가 됩니다. (기본값은 16)
이번 문제에서는 주어진 cacheSize 이상의 데이터가 들어가지 않을 것이기 때문에 초기값을 cacheSize로 설정했습니다. -
loadFactor : "총 수용 가능한 element 수 / capacity" 입니다.
HashMap에 element가 추가될 때 전체 element 수가 (loadFactor * capacity)를 넘어가게 되면, HashMap은 capacity를 2배로 늘리고 모든 element를 bucket들에 다시 분배하는 rehashing을 하게 됩니다. 이 과정의 overhead가 매우 크기 때문에 되도록 일어나지 않게 해야합니다. 따라서 처음에 들어갈 데이터의 용량을 예상하여 capacity와 loadfactor를 잘 설정하는 것이 중요합니다.
일반적으로 최적은 0.75f이므로 그대로 설정해주었습니다. -
accessOrder : 이번 문제에서 중요하게 작용하는 매개변수입니다.
- false이면 insertion-order, 즉 put()하는 순서로만 순서가 정해집니다. 어떤 key에 대해 get()을 해도, 그 key의 순서는 처음 추가했을 때에 순서에서 달라지지 않습니다. 새로 갱신하고 싶으면 remove() -> 다시 put()을 해야 합니다.
- true이면 access-order, 즉 put()과 get()하는 순서로 순서가 정해집니다. 따라서 put()할 때는 물론, get() 할 때도 해당 key의 순서가 갱신됩니다.
LRU 방식으로 작동하기 위해서 해당 entry를 사용(put() & get())했을 때 순위가 갱신되어야 하기 때문에 true로 설정해주었습니다.
2. removeEldestEntry
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > cacheSize;
}put()을 호출할 때마다 호출되며, return값이 true이면 가장 오래된 Entry를 제거하는 함수입니다.
매개변수 eldest는 가장 오래된 entry입니다. 여기서는 access-order mode로 생성했기 때문에, 매개변수인 eldest는 추가 or 조회된 지 가장 오래된 entry가 됩니다.
size(), 즉 entry의 갯수가 cacheSize보다 크면 true를 return하여 가장 오래된 entry를 삭제하고 새로운 entry를 추가하게 함으로써, LRU 캐시를 구현했습니다.
나머지 풀이
String name;
for (String city : cities) {
name = city.toUpperCase();
if (cache.get(name) == null) {
answer += 5;
cache.put(name, "");
} else
answer += 1;
}cities 배열의 각 도시들에 대해 대소문자 구분을 없애기 위해 대문자로 변환한 뒤, cache miss일 땐 +5, cache hit일 땐 +1을 해주는 방식으로 문제를 해결할 수 있었습니다.
전체 코드
import java.util.Map;
import java.util.LinkedHashMap;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
Map<String, String> cache = new LinkedHashMap<>(cacheSize, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > cacheSize;
}
};
String name;
for (String city : cities) {
name = city.toUpperCase();
if (cache.get(name) == null) {
answer += 5;
cache.put(name, "");
} else
answer += 1;
}
return answer;
}
}