문제에서 예외 케이스까지 친절하게 알려줬고 로직 자체는 어렵지 않았는데, 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은 중복을 허용하지 않고 삽입 순서를 기억한다. 그래서 테스트 코드 몇 줄 써봤는데, '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 의 사용을 한 번 더 정리해보고, 코드를 수정한 후에는 실행에 급급하지 말고 제대로 수정한 게 맞는지 확인해봐야겠다.
끝!