[KAKAO BLIND RECRUITMENT] 캐시

🗒️ 문제

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

💬 입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

💬 출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

📎 조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

캐시크기(cacheSize)	도시이름(cities)	실행시간
3	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	50
3	["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]	21
2	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	60
5	["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]	52
2	["Jeju", "Pangyo", "NewYork", "newyork"]	16
0	["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]	25

📝 문제 해설

문제를 몇번 다시 읽어봐도 정확하게 무엇을 구하고자 하는지 파악하기가 힘들다. LRU 알고리즘을 사용하라고 하는데 여기서 LRU에서 cache hit은 두개의 배열 중에서 하나의 배열이 다른 배열에도 있다면 cache에 있는 해다 원소값을 제거하고 뒤에 맨 뒤에 해당 원소값을 push하는 방식이고, cache miss는 cache에 찾는 배열이 없을 경우에 가장 오래전에 들어간 원소값(인덱스 0값)을 제거하고 뒤에 새로운 원소를 push하는 방식이다.

우선 대소문자 구분을 하지 않는다고 하였으므로 모든 문자를 소문자로 바꿔준다. 다음으로 for문과 if문을 사용하여 cache에 원소값이 있는 경우와 없는 경우를 나누어 배열에 원소값이 있으면 해당 원소값을 indexOf()을 이용하여 찾고 splice()로 제거한다. 만약 없다면 shift()로 가장 오래 전에 input된 원소를 제거하고 새로운 원소 값을 push해준다.

처음에는 for문을 두번 사용하였더니 테스트 케이스는 통과했지만 시간초과가 계속 떴다. 그리고 알 수 없는 오류가 발생하였다. for문 하나를 이용하고 주석을 활용해서 코드를 구조화하였더니 시간초과는 해결되었지만 이번에는 또 케이스 11, 19, 20번에서만 오류가 났다.

생각을 해보니 처음에 cache의 size가 cacheSize가 될 때까지 push만 해주었는데 여기서 만약에 이미 원소가 들어있는 경우가 있다면 중복된 값을 계속해서 push해주는 꼴이 되어버린다. 따라서 cacheSize가 될때 까지 push하는 과정에서도 예외처리를 해줘야만 모든 케이스가 정상적으로 통과된다.

💡 필요 문법

shift()

가장 처음에 들어간 원소값을 제거하는 방식이다. 보통 index 0번을 제거한다.

indexOf()

배열에서 원하는 값의 인덱스 값을 반환해준다. 하지만 찾는 원소가 배열에 없다면 -1 값을 리턴한다.

push()

배열에 가장 끝에 새로운 원소 값을 넣어준다.

splice(a,b)

a번째 index에 있는 원소부터 b개 제거한다. 배열의 특정값을 제거할 때 사용된다.

💻 코드

function solution(cacheSize, cities) {
    cities = cities.map(v => v.toLowerCase());
    let cache = [];
    let time = 0;
    
    for(let i=0; i<cities.length; i++){
        if(cacheSize === 0) time = cities.length * 5;
        
        // 캐시가 빈칸일 때 캐시사이즈가 찰 때까지 push 해주기
        else if(cache.length < cacheSize){
            if(cache.indexOf(cities[i]) !== -1){
                cache.splice(cache.indexOf(cities[i]), 1);
                time += 1;
                cache.push(cities[i]);
            }
            else{
                cache.push(cities[i]);
                time += 5;
            }
        }
        else if(cache.length === cacheSize){
            // 캐시에 도시 이름이 있는 경우 
            if(cache.indexOf(cities[i]) !== -1){
                cache.splice(cache.indexOf(cities[i]), 1);
                time += 1;
                cache.push(cities[i]);
            }
            // 캐시에 도시 이름이 없는 경우
            else if(cache.indexOf(cities[i]) === -1){
                cache.shift();
                time += 5;
                cache.push(cities[i]);
            }
        }
    }
    return time;
}