[programmers] 캐시 (in JS)
문제
캐시-2018 kakao blind recruitment
- 캐시 크기와 도시 이름 배열을 입력받는다.
- 도시 이름은 영문자로 구성되며, 대소문자를 구분하지 않는다.
- 캐시 교체 알고리즘은 LRU를 사용한다.
- cache hit은 실행시간 1이고, cache miss는 실행시간 5이다.
- 도시 이름 배열을 순서대로 처리할 때, '총 실행시간'을 출력한다.
Fact
- 도시 이름은 대소문자를 구분하지 않으므로, 대문자나 소문자로 고정하여 캐쉬에 저장하여야 한다.
- 캐시 크기가 0이면 어떠한 도시라도 캐시 미스가 발생한다.
- 캐시에 도시가 다 채워져있을 때, 캐시 미스가 발생하면 가장 오랫동안 사용이 안된 도시를 캐시에서 지워야 한다.
- 가장 최근에 사용된 도시는 캐시의 맨 뒤에 저장한다면, 캐시의 첫 번째는 가장 오랫동안 사용되지 않은 도시이다. 이 도시가 캐시 미스가 되었을 때 교체 대상이 된다.
접근
도시는 대소문자를 구분하지 않으므로, 입력받은 도시이름 배열에서 모든 도시를 소문자로 변환한다.
가장 최근에 사용된 도시는 캐시의 맨 뒤에 저장하도록 하였다.
맨 앞에 있는 도시는 캐시 미스시 교체 대상이 되는 도시이다.
도시가 캐시에 있다면, 캐시에 있는 도시는 가장 최근에 사용된 것이므로, 위치를 캐시의 맨 뒤로 옮긴다.
도시가 캐시에 없을 땐, 캐쉬의 맨 뒤에 도시를 추가해야 한다. 그 전에, 캐시에 있는 도시의 수가 캐시 크기를 이상인지 확인해야 한다. 도시의 수가 캐시 크기 이상이라면, 캐시에서 가장 앞에 있는 도시를 삭제한다. 그 후, 캐쉬의 맨 뒤에 도시를 추가한다.
복잡도
- 공간 복잡도 : O(k), k는 0이상 30이하
- 시간 복잡도 : O(N)
- 도시이름 배열을 처음부터 끝까지 순회한다.
알게된 점
- 배열의 첫 번째 요소를 삭제하는 메서드는 Array.prototype.shift()이다.이 메서드는 기존 배열을 변형한다.
- 배열의 앞에 요소를 추가하는 Array.prototype.unshift()이다. 이 메서드 또한 기존 배열을 변형한다.
코드
const HIT = 1;
const MISS = 5;
const isInCache = (cityList, target) =>
cityList.some((city) => city === target);
const removeFromCache = (cityList, target) =>
cityList.filter((city) => city !== target);
function solution(cacheSize, cities) {
if (cacheSize === 0) {
return cities.length * MISS;
}
const lowCities = cities.map((city) => city.toLowerCase());
let cache = [];
const totalTime = lowCities.reduce((time, city) => {
if (isInCache(cache, city)) {
cache = [...removeFromCache(cache, city), city];
return time + HIT;
}
if (cache.length >= cacheSize) {
cache.shift();
}
cache.push(city);
return time + MISS;
}, 0);
return totalTime;
}
Author And Source
이 문제에 관하여([programmers] 캐시 (in JS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yejineee/programmers-캐시-in-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)