2022/03/15) 5. Least Recently Used(카카오 캐시 문제 변형) [정렬과 그리디, 결정알고리즘]

1. 문제

<.Least Recently Used>
: 만약 캐시의 사이즈가 5이고 작업이 [2, 3, 1, 6, 7] 순으로 저장되어 있다면, 새로운 작업이 들어올 때 만약 해야할 작업에 포함돼 있지 않다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 새로운 작업은 맨 앞으로 간다. 혹은 새로운 작업이 만약 해야할 작업에 포함돼 있다면 Cache Hit이 되고 해야할 작업이 맨 앞으로 가고 나머지 작업들은 뒤로 밀린다.

2. 해결 방법

1. 캐시의 사이즈가 5란걸 생각하자! Array.from({length:size},()=>0)으로 배열 생성
2. forEach로 arr배열을 돌리는데, hit가 났는지 안났는지 확인하기 위해 pos = -1을 선언한다.(인덱스번호 -1은 없으므로, -1로 선언)
3. 그리고 그 안에서 for문을 돌려서 hit인지 아닌지 확인한다. hit면 pos = i로 해준다. 헷갈리는데 정리하자면 'forEach : 1이 들어온다. -> for : 새로 만든 배열(answer)의 내용과 겹치는지 확인'하는 것이다.
4. miss일때는 뒤로 땡기고 땡기고 땡겨주고, hit일때는 pos부터 땡기고 땡기고!
5. 마지막에 x값을 answer[0]에 넣어준다.

3. 정답

        <script>
            function solution(size, arr){
                let answer = Array.from({length:size}, () => 0);
                arr.forEach(x => {
                    let pos = -1;
                    for(let i = 0; i < answer.size; i ++) if(x===answer[i]) pos = i; //hit났을 경우! hit가 안나면 -1임
                    if(pos === -1){ //miss난 상황
                        for(let i = size-1; i >= 1; i --){
                            answer[i] = answer[i-1];
                        }
                    }
                    else{ //hit상황
                        for(let i = pos; i >= 1; i --){
                            answer[i] = answer[i-1];
                        }
                    }
                    answer[0] = x;
                })
            }
            let arr=[1, 2, 3, 2, 6, 2, 3, 5, 7];
            console.log(solution(5, arr));
        </script>
    </body>

        <script>
            function solution(size, arr){
                let answer = Array.from({length:size}, () => 0);
                arr.forEach(x => {
                    let pos = -1;
                    for(let i = 0; i < size; i ++) if(x===answer[i]) pos = i; //hit났을 경우! hit가 안나면 -1임
                    if(pos === -1){ //miss난 상황
                        answer.unshift(x);
                        if(answer.length>size) answer.pop() ;
                    }
                    else{ //hit상황
                        answer.splice(pos, 1);
                        answer.unshift(x)
                    }
                    answer[0] = x;
                })
                return answer;
            }
            let arr=[1, 2, 3, 2, 6, 2, 3, 5, 7];
            console.log(solution(5, arr));
        </script>