[JS] 2018 KAKAO BLIND RECRUITMENT > [1차] 캐시

function solution(cacheSize, cities) {
    var answer = [];
    var time = 0;
    cities = cities.map(v=> v.toLowerCase());
    
    if(cacheSize == 0){
        return cities.length * 5;
    }
    
    while(cities.length){   
    
        var city = cities.shift();

        //캐시가 가득 찼을 때
        if(answer.length == cacheSize){
            
            if(answer.indexOf(city) != -1){
                answer.splice(answer.indexOf(city), 1); 
                time += 1;               
            }else{
                answer.shift();
                time += 5;
            }  
            
        //캐시에 공간이 있을 때    
        }else if(answer.length < cacheSize){
            
            if(answer.indexOf(city) != -1){
                answer.splice(answer.indexOf(city), 1);
                time += 1;
            }else{
                time += 5;
            }  
        } 
        answer.push(city);
    }
    return time;
}

 

 

cities의 값에 LA, la처럼 대소문자가 혼용되어 있어서 모두 소문자로 변경을 해준다.

만약에 캐시 사이즈가 0이라면 cities의 값을 넣었을 때 계속 miss가 되기 때문에 cities의 길이만큼 5를 곱해서 리턴을 해준다.

0 처리를 해주고, cities에 값이 있을 때까지 반복을 돌려준다.

제일 처음 값을 shift로 받아와 변수 city에 저장해줬다.

//캐시가 가득 찼을 때
if(answer.length == cacheSize){
            
            if(answer.indexOf(city) != -1){
                answer.splice(answer.indexOf(city), 1); 
                time += 1;               
            }else{
                answer.shift();
                time += 5;
            }
//...
 answer.push(city);

캐시가 가득 찼다면 city에 있는 값이 캐시에 이미 들어가 있다면 data hit가 뜨기에 time을 1 올려준다.

이때 주의해야 할 점이 기존에 있던 값은 없어지고 새롭게 캐시에 값이 들어가야 한다.

예를 들어 캐시에 [1,2,3]이 있을 때 새로운 값 2가 들어가면 hit가 뜨면서 [1,3,2]의 형태로 캐시에 저장이 된다.

캐시에 값이 없다면 제일 앞의 값을 없애고 data miss가 뜨기에 5를 더해준다.

time을 더해주는 과정이 끝나고 새로운 city를 push해준다.

//캐시에 공간이 있을 때    
        }else if(answer.length < cacheSize){
            
            if(answer.indexOf(city) != -1){
                answer.splice(answer.indexOf(city), 1);
                time += 1;
                
            }else{
                time += 5;
            }  
        } 
        answer.push(city);

캐시에 공간이 있을 때에도 city가 캐시에 들어있는지 확인을 하고 time 계산을 해준다.

이때 다른 점은 캐시에 city가 없을 때, 공간이 있기 때문에 shift를 안 해줘도 된다.

time을 더해주는 과정이 끝나고 새로운 city를 push해준다.

 

LRU 알고리즘은 정처기 공부할 때만 알았던 개념이었는데 직접 써보니까 재밌다

다른 페이지 교체 알고리즘도 공부하기-!!