[230420] 캐시

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

 

 

풀이

첫 번째 풀이 (실패)

캐시 교체 알고리즘은 LRU (Least Recently Used) 라 했으니,

가장 먼저 캐시에 들어간 도시이름이 가장 먼저 교체되는 형태라 생각해서 Queue를 활용해서 풀면 되겠다 생각했다.

function solution(cacheSize, cities) {
    cities = cities.map(city => city.toLowerCase());
    
    let answer = cacheSize * 5;
    
    while(cities.length > cacheSize) { 
        if(cities.slice(0, cacheSize).includes(cities[cacheSize])) answer += 1;
        else answer += 5;
        
        cities.shift();
    }
    return answer;
}

1. 도시 이름은 대소문자를 구분하지 않는다 했으므로 toLowerCase() 로 소문자로 모두 통일시켜준다.
2. 처음 캐시 크기만큼은 캐시에 아무것도 없으므로 무조건 5다. 그래서 answer = cacheSize * 5 로 시작한다.
3. cities 배열의 0 ~ cacheSize 만큼 보고, 캐시에 들어갈 도시 이름이 캐시에 있으면 hit 이므로 answer += 1, 없으면 miss이므로 answer += 5 한다.
4. cities 배열의 가장 앞부분을 shift 한다.
5. 3~4 과정을 cities 배열의 크기가 cacheSize보다 클 때까지 반복한다.

테스트 9, 11, 15, 16, 18, 19, 20에서 실패한다.

 

 

생각해보니 문제점이 두 가지가 있었는데,

첫 번째는, 제일 처음 cacheSize 만큼 들어올 때 무조건 answer = 5 * cacheSize 처리를 해줬던게 잘못 생각했던 부분이었다. 앞에서도 중복된 도시 이름이 들어올 수도 있기 때문이다.

두 번째는, 큐로 접근한 점이다. 이게 큰 실수였다. ‘제주’가 캐시의 3번째 인덱스에 있을 때 ‘제주’가 들어와서 hit이 된 경우, 3번째 인덱스가 나가고 캐시의 가장 뒤로 ‘제주’가 추가되어야 한다.

테스트 6개는 우연히 운이 좋아서 모두 통과된 것이었다. 암튼 그래서 다시 풀었다.

 

 

 

 

두 번째 풀이

function solution(cacheSize, cities) {
    cities = [...new Array(cacheSize).fill(), ...cities.map(city => city.toLowerCase())]; 
    
    let answer = 0;
    
    while(cities.length > cacheSize) { 
        if(cities.slice(0, cacheSize).includes(cities[cacheSize])) {
            answer += 1;
            cities.splice(cities.indexOf(cities[cacheSize]), 1);
        } else {
            answer += 5;
            cities.shift();
        }
    }
    return answer;
}

이전과 비슷한 형태이긴 한데, cities 배열 앞에 cacheSize 만큼 빈 배열을 넣었다.

그리고 hit 일 때는 indexOf와 splice를 이용해서 해당 요소를 없앴고,

miss 일 때는 동일하게 shift로 맨 앞 요소를 없앴다.

끝

 

근데 점수는 어떨 때 많이 받는거지..