[lv2] 캐시

문제링크

• cacheSize : 캐시 크기, cities : 도시 이름의 배열
• cache hit = 1 (캐시값이 남아있는 경우 걸리는 시간)
  cache miss = 5 (캐시값이 없는 경우 걸리는 시간)
• 캐시 교체 알고리즘 : LRU (오래된 기록부터 제거)
• 캐시 크기에 따른 실행시간 return

큐[선입선출 방식] 사용
이미 있는 기록의 경우 splice로 제거 후 다시 push

function solution(cacheSize, cities) {
    // cities를 shift()로 빼서 방문기록 배열에 추가.
    // 방문 기록의 길이가 cacheSize보다 커지면 방문기록에 shift() 실행
    // cities.shift()가 방문기록 배열에 있으면 splice 사용 제거, 다시 push
    // 방문기록.splice(변경할 값의 위치, 1) -> 방문기록에 push
    let times = 0;
    const visited = []
    // shift를 사용하면 cities의 배열이 변동되어 length값이 일정하지 않음 -> cities.length값을 사용하는 for 반복문 사용 불가
    while(cities.length > 0){
        const key = cities.shift().toUpperCase(); // 대소문자를 구분하지 않으므로 통일
        let idx = visited.indexOf(key);
        // 인덱스값이 필요하니까 incldues 대신 indexOf 사용
        if(idx < 0){
            // 방문기록이 없는 경우
            times+=5;
            visited.push(key)
            if(visited.length > cacheSize){
                // 방문기록이 캐시사이즈를 넘긴 경우
                visited.shift();
            }
        } else {
            // 이미 방문기록이 있는 경우
            times += 1;
            visited.splice(idx,1)
            visited.push(key)
        }
    }
    return times
}

다른 사람의 풀이

function solution(cacheSize, cities) {
    const MISS = 5, HIT = 1;
    if (cacheSize === 0) return MISS * cities.length;
    let answer = 0,
        cache = [];
    cities.forEach(city => {
        city = city.toUpperCase();
        let idx = cache.indexOf(city);
        if (idx > -1) {
            cache.splice(idx, 1);
            answer += HIT;
        } else {
            if (cache.length >= cacheSize) cache.shift();
            answer += MISS;
        }
        cache.push(city);
    });
    return answer;
}

cacheSize가 0인 경우 설정,
while 대신 forEach를 사용해서 문제 해결

다른 사람의 풀이2

function solution(cacheSize, cities) {
    const map = new Map();
    const cacheHit = (city, map) => {
        map.delete(city);
        map.set(city, city);
        return 1;
    };
    const cacheMiss = (city, map, size) => {
        if(size === 0) return 5;
        (map.size === size) && map.delete(map.keys().next().value);
        map.set(city, city);
        return 5;
    };
    const getTimeCache = (city, map, size) => (map.has(city.toLocaleLowerCase()) ? cacheHit : cacheMiss)(city.toLocaleLowerCase(), map, size);
    return cities.map(city => getTimeCache(city.toLocaleLowerCase(), map, cacheSize)).reduce( (a, c) => a + c, 0);
}

Map을 사용한 방식
hit과 miss를 함수로 구분해서 실행