문제에서 예외 케이스까지 친절하게 알려줬고 로직 자체는 어렵지 않았는데, LRU 알고리즘에 대해 알아야 풀 수 있는 문제였다.
LRU 알고리즘
캐시(페이지) 교체 알고리즘 중 하나로, Least Recently Used의 약자이다. 새로운 데이터가 발생했을 때, 가장 오래전에 사용된 데이터를 제거하고 새로운 데이터를 삽입하는 알고리즘.
1. 새로운 데이터가 들어온 경우
1-1. 캐시에 넣어준다.
1-2. 캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다.
2. 존재하는 데이터가 들어온 경우
2-1. 해당 데이터를 꺼낸 뒤,
2-2. 가장 최근 데이터 위치로 보내준다.queue 알고리즘을 사용하면 쉽게 구현할 수 있다.
설계
처음에는 위에 쓴대로 1. if -> if / if 2. if -> if / if (else를 안쓰려는 노력) 이렇게 작성하려고 했으나 좀 더 인덴트를 줄여보고자 4가지 조건을 다 같은 인덴트의 if문으로 처리하기로 결정! 그러다가 주황색 박스 친 부분의 조건이 같은 것을 발견해서 3가지 조건으로 정리할 수 있었다.
배열이 아닌 Set을 사용한 이유
알고리즘 구현 시 배열을 안 쓰고 Set을 사용했다. Set은 중복을 허용하지 않고 삽입 순서를 기억한다. 그래서 테스트 코드 몇 줄 써봤는데, 'a', 'b', 'c'를 차례로 Set에 add하고 다시 'a'를 add하면 순서는 여전히 a, b, c이다. 즉, a를 맨 뒤로 보내려면 Set에서 삭제한 뒤 다시 add해야 한다.
그럼에도 Set으로 구현한 이유는 맨 마지막 요소가 아닌 요소를 제거해야한다면 Set이 더 효율적이지 않을까 하는 생각이 들어서이다. (이 문제에서는 맨 앞의 요소를 제거하면 되기 때문에 배열 메서드의 shift()를 사용하면 돼서 크게 상관이 없는 것 같기도..) 실제로 더 효율적인지는 잘 모르겠다. Map과 Object를 비교했을 때에는 값을 추가, 제거하는 것에 있어서 Map이 더 효율적이라고 알고 있는데 Set은 잘 모르겠다. (댓글로 알려주시면 무한 감사.. 😁)
코드
function solution(cacheSize, cities) {
let executionTime = 0;
let cacheSet = new Set();
// cacheSize 0인 경우
if(cacheSize === 0) return cities.length * 5;
const lowerCaseCities = cities.map(city => city.toLowerCase());
lowerCaseCities.forEach(city => {
// cache hit
if(cacheSet.has(city) === true) {
executionTime += 1;
cacheSet.delete(city);
cacheSet.add(city);
}
// cache miss
// cacheSet size < cacheSize 일 때
if(cacheSet.has(city) === false && cacheSet.size < cacheSize) {
executionTime += 5;
cacheSet.add(city);
}
// cacheSet size = cacheSize 일 때
if(cacheSet.has(city) === false && cacheSet.size === cacheSize) {
executionTime += 5;
cacheSet.delete(Array.from(cacheSet)[0]);
cacheSet.add(city);
}
})
return executionTime;
}삽질
-
문제에서 주어진 입력값은 대소문자를 구분하지 않기 때문에 모두 대문자나 소문자로 바꿔주는 과정이 필요했다. 처음에는
cities.forEach(city => city.toLowerCase());라고 썼다가 잘 안 돼서map으로 바꾼 후 변수에 할당했다. 요즘 왜 이렇게forEach와map이 헷갈릴까? ㅠㅠ -
1번을 해결하기 전에 if문 3개 들어있는 부분에서 뭔가 어쩌다가 조건에 2개 걸리나 싶어서
break를 걸어야하나 싶었다. (break를 걸면 반복문을 아예 탈출하는 거라 사실 break도 틀리긴 했음) 그런데forEach에는break가 없다고 해서 괜히for문으로 바꿔보고continue키워드도 넣어보고 했는데 다시 보니if조건에 중복으로 걸릴 일이 없겠다는 생각이 들었다. 그 후로 1번 삽질 해결함..! -
그밖에도
cacheSet.delete(Array.from(cacheSet[0]));이라고 쓴다거나 forEach와 for문을 변경하면서 지역변수를 같이 안바꿔줬다거나 하는 자잘한 삽질들을 너무 많이 해서 시간이 오래 걸렸다.. 😞 아 사실 캐시사이즈가 0인 예외조건도 맨 나중에 넣긴 했다. 예외조건을 꼼꼼히 확인하고, map / forEach 의 사용을 한 번 더 정리해보고, 코드를 수정한 후에는 실행에 급급하지 말고 제대로 수정한 게 맞는지 확인해봐야겠다.
끝!
