프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
해당 문제를 풀기 위해서는 LRU가 무엇인지 먼저 알아야 한다.
LRU(Least Recently Used)
- 가장 오랫동안 사용되지 않은 데이터를 제거하는 기법
- 주로 캐시 메모리 관리나 페이지 교체 알고리즘에 사용
LRU의 사전적 의미는 이러하고 어떻게 진행되는지 이해하기 쉽게 알아보자
값이 들어갈 수 있는 3개의 칸이 캐시의 크기이다.
찾으려고 하는 값이 캐시에서 찾을 수 있는 경우 hit, 그렇지 않은 경우 miss이다.
먼저 1,2,3의 경우 캐시에서 값을 찾을 수 없지만 캐시에 남는 공간이 있기에 각각의 값이 캐시에 추가가 된다.
해당 과정에서는 캐시에서 값을 찾을 수 없기에 모두 miss처리이다.
다음으로 4의 경우 마찬가지로 miss이지만 cash가 꽉 찬 경우이다.
LRU는 이전에 설명하였듯이 가장 오랫동안 사용되지 않은 데이터를 제거하는 방식이다.
현재로는 1,2,3의 순서로 값이 저장되었기에 가장 오래된 값은 1이므로 해당 값을 제거하고 4의 값이 추가되는 방식으로 진행된다.
마찬가지로 다음순번의 1,2가 똑같이 진행된다.
마지막 4의 값을 수행하기전 캐시의 상태는 4,1,2의 값이 저장되어 있는 상태이다.
해당 상태에서 4의 값이 바로 조회 가능하기에 이번에는 hit가 되는 것이다.
그럼 이를 어떻게 문제를 풀기위해 코드로 구현을 할 수 있을까?
해당 문제에서 사용할 cacheSize와 cities라는 도시의 이름이 담긴 String형 배열이 제공이 된다.
나는 이를 해결하기 위해 LinkedList를 이용하였다.
public static int solution(int cacheSize, String[] cities) {
int answer = 0;
LinkedList<String> ll = new LinkedList<>();
if (cacheSize == 0)
return 5 * cities.length;
// 도시를 먼저 대문자로 모두 설정
for (int i = 0; i < cities.length; i++) {
cities[i] = cities[i].toUpperCase();
}
for (String c : cities) {
if (!ll.isEmpty()) {
// 1. ll안에 이 값이 들어있는 경우 hit
if (ll.contains(c)) {
//들어있는 값을 제거하고 다시 등록해줌에 따라 최신화 -> 오래된 것일수록 앞쪽에 위치하도록 설정
ll.remove(c);
ll.add(c);
answer += 1;
} else { // else인 상황에 ll에는 c값이 들어있지 않아 이미 miss인 상황
if (ll.size() < cacheSize) {// 2-1 miss이지만 ll이 꽉 차지 않은 경우
ll.add(c);
answer += 5;
} else {// 2-2 miss 이면서 ll이 꽉 차있는 경우
ll.remove(0);
ll.add(c);
answer += 5;
}
}
} else { // ll이 비어있으면 무조건 miss이므로 +5
ll.add(c);
answer += 5;
}
}
return answer;
}
캐시 사이즈가 0인경우 무조건 miss이므로 해당 문제에서 miss일 경우 걸리는 시간인 5를 계산하여 배열의 크기만큼 곱해주었다.
그렇지 않은 경우는 for문을 이용하여 배열을 돌면서 LinkedList에 값을 추가하고 제거하는 방식으로 구현을 하였다.
ArrayList도 작동하는건 마찬가지겠지만 시간복잡도 측면에서 차이가 있다.
ArrayList는 삽입이나 제거를 수행하고나면 해당 배열을 재구성하는 방식으로 O(n)의 시간 복잡도가 걸리게 된다.
하지만 LinkedList는 삽입 또는 제거를 수행할때 배열을 재구성하는것이 아닌 연결된 링크만 수정하게 되므로 O(1)의 시간 복잡도를 가진다.
따라서 삽입과 제거가 많이 일어나는 작업이라 판단하여 ArrayList대신 LinkedList를 이용하여 구현하였다.
상세한 내부 로직은 코드를 직접 보거나 적어보며 학습하길 바란다.