접근
우선, LRU(Least Recently Used)가 뭔지 간단하게 알아보자.
LRU(Least Recently Used Cache)는 오랫동안 사용하지 않은 데이터 부터 없애는 방법
Double Linked List를 사용할 경우 입력값 [1,2,3]에 대해 1 / 2 -> 1 / 3 -> 2 -> 1과 같은 방식으로 저장함
즉 최근에 사용한게 맨 앞에 위치
여기서 cacheSize가 3이고 입력값이 추가로 4가 들어오면 4->3->2가 된다.
그래서 다음과 같이 생각해 보았다.
도시이름 순회
도시가 cache에 있는지 확인
있다면 2가지 경우로 나뉨
발견된 index의 값을 저장 하고 앞에 있는 것들을 한칸씩 민다.
그다음 저장한 값을 맨 앞에 저장
없다면 우선, cacheSize가 0인지 예외처리를 해준다.
0이라면 cache에 아무 값도 들어가면 안된다.
아니라면 한 칸씩 밀고 맨 앞에 값 넣기
마지막으로, cache 크기와 cacheSize를 비교한다 cache 배열의 크기가 더 크면 pop()
function solution(cacheSize, cities) {
var answer = 0, cache = [];
const hit = 1, miss =5;
for(let city of cities){
// 대소문자 구분 없이 처리하기 위함.
city = city.toLowerCase();
// cache에서 city의 index를 찾는다.
let idx = cache.indexOf(city);
// cache에 city가 있음
if(idx > -1){
answer += hit;
// city값 저장
let temp = cache[idx];
// 한칸씩 밀기 ex) [a,b,c]이고 city이름이 c라면 [c,a,b]로 만들기 위함
for(let i=idx; i>0; i--){
cache[i] = cache[i-1];
}
cache[0] = temp;
} else{ // 없음
answer += miss;
//cacheSize가 0일때 예외 처리
if(cacheSize != 0) {
cache.unshift(city);
// 과하게 memory 점유하지 않게 필요 없는건 pop();
if(cache.length > cacheSize) cache.pop();
}
}
}
return answer;
}
후기
처음에 접근할 때는 LRU 구현 코드가 있었는데 이것을 사용하지 않고 다른 방법을 사용해야 하는 줄 알았다. 그러다 배열을 이용하여 사용하게 되었는데 결론적으로 LRU보다는 시간 복잡도가 좋지는 않다. LRU 같은 경우에는 추가의 경우 O(1)인데 배열을 이용하면 모든 값을 뒤로 밀고 맨 앞에 값을 넣기 때문에 O(n)이다.
근데 카카오 해설을 보니까 검색해서 가져다 써도 되지만 마지막 0에 대한 예외 처리를 해야 한다고 되어 있었다.
음.. 가져다 써도 되는 거였네...
