[프로그래머스] 캐시

처리조건

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

풀이

LRU란 정해진 캐시크기로 만들어진 캐시에 데이터가 쌓여있을 때 새로운 데이터를 쌓으려면 1개를 내보내고 넣어야하는데 누굴 내보낼까 한다면 안에 든 데이터중 가장 먼저 들어온 즉, 오래놓안 엉덩이를 눌러붙이고 있었던, 가장 무관심속에 있었던 데이터를 내보내야한다 그리고 그 자리에 새로운 데이터를 쌓을것이다. 만약 쌓으려는 데이터가 또 쌓인 데이터중에 동일한 값이 있을 수 있다. 그럴경우 그자리를 그냥 그대로 사용한다.

 

이러한 경우에서 엉덩이를 눌러붙이고 있던 오래된 데이터를 교체하게 되면 Cache miss, 만약 있던 데이터를 그대로 사용하게된다면 cache hit이다. 처리조건에서 miss는 5초를 더하고 hit는 1초를 더하면된다.

 

우선 시간을 쌓기 위해 time으로 0을 할당했고 cache를 배열로 만들어줬다. 자. 이제 cities를 하나씩 for문으로 풀어 cache에 쌓아보자. 여기서 잠깐! 만약 cacheSize가 0으로 들어왔다면 사실상 cities에서 들어가길 기다리는 데이터들이 들어갈 자리가 없으므로 hit가 아니라 모두 miss가 된다 그래서 cities길이만큼 5를 곱하여 리턴해주면된다. 그외에 cacheSize가 0이상이면 그래도~ 들어갈 자리가 있으니까 로직을 작성해보자

 

for문으로 cities의 길이만큼 돌리자. 처리조건에서 대소문자 구분이 없으니 한번 돌때마다 cities안에 든 요소는 소문자 처리 해준다. 이제 if문으로 들어갈 조건을 필터해줄건데 cache안에 지금 들어갈 cities[i]가 존재한다면 해당 요소를 splice로 삭제하고 시간을 1초올린다 hit이기 때문에 이제 이 데이터에 관심을줬고 엉덩이를 땠다가 다시 붙였다.. 그러니 처리가 끝날때 cache 맨뒤에 다시쌓는다. 이러한 구조는 cache 맨앞에 있을수록 가장 오랜동안 안에서 무관심속에서 지내온 데이터이다. 

 

else문에서는 안에 동일한 데이터가 없으니 miss처리가 될 곳이다. 넣기전에 cacheSize와 현재 cache배열의 길이를 검사한다. 왜냐? 길이가 같으면 넣을자리가 없으니 가장 오랜동안 엉덩이를 붙인, 맨앞에 있는 요소를 제거해야 한자리가 남는다. 그래서 shift()를 통해 cache의 맨 앞 요소를 제거한다. 만약 같지 않으면 공간이 있다는 것이다 shift 하지않고 나온다. 끝으로 miss이니 5초를 올려준다. 그리고 for문이 끝날 때 hit 처럼 cache 배열 맨 위에 들어갈 요소를 push 해준다.

 

다끝나고 나서 time을 리턴해준다.

 

이 문제는 LRU를 먼저 알아야하고 HIT와 MISS가 무엇인지 알아야한다. 처음 입출력 예제에서 맨 처음 케이스를 수기로 적어서 실행시간을 검사해보니 50시간보다 적게나왔다. 이유가 뭘까 생각해보니 cache에 하나도 안쌓인 상태에서 처음 데이터를 쌓기 시작하면 캐시 크기만큼 쌓이는데 이때 처음 들어오는 데이터들도 안에 어찌됐건 중복된 데이터가 없으니 miss르 봐야한다. 나는 이걸 hit로 보는 바람에 실행 시간이 적게 나왔다.

 

그리고 가장 오래된 데이터를 교체해야한다는 점에서 어디에 그데이터가 존재할까를 데이터를 맨앞으로 이동한다는 점으로 오래된 데이터는 앞으로 간다는 조건을 잘 생각해서 로직을 짜야한다.

function solution(cacheSize, cities) {
    let time =0 ;
    let cache=[]
    
    if(cacheSize ===0) return cities.length * 5
    
    for(let i=0 ; i<cities.length ; i++){
         
        cities[i] = cities[i].toLowerCase();
        if(cache.includes(cities[i])){
            cache.splice(cache.indexOf(cities[i]),1)
            time+=1
        }
        else{
            if(cacheSize===cache.length){
                cache.shift()
             
            }
               time+=5
        }
        cache.push(cities[i])
    }
    return time
}