알고리즘 - LRU알고리즘

출처 : 제주코딩베이스캠프 94번

이 알고리즘은 제일 마지막으로 쓰인 것을 없애고 새로운 데이터를 넣어주는 알고리즘이다.

(폐기 찍는 느낌으로 해야하나..)

실제 답안에서는, memory 배열 하나만 사용해서 답을 풀었는데, (아마 실행시간을 출력하는게 답이라서 그런 것 같다)

나는 memory 배열과, 쓰이지 않는 데이터를 제외한 나머지가 있는 배열

0. 쓰이지 않는 데이터가 없는 배열에서

1. 배열의 맨 앞에 있는 데이터를 shift() 해준다

2. 그리고 들어오는 데이터를 push() 해준다.

3. shift() 를 변수로 선언 하면 그게 바로 쓰이지 않는 데이터가 된다.

4. 그 데이터를 memory 배열에서 찾고 들어오는 데이터를 그자리에 넣어주면 된다.

const incomingPages = 'B C B A E B C E'.split(' ');
const frame = 3;
let time = 0;
const memory = [];

const lru = [];

while(incomingPages.length > 0) {
    const incomingPage = incomingPages.shift();

    if(memory.includes(incomingPage)) {
        lru.shift();
        time = time + 1
    } else {
        if(memory.length === frame) {
            const index = memory.indexOf(lru.shift())
            memory.splice(index, 1, incomingPage);
        } else {
            memory.push(incomingPage)
        }
        time = time + 6
    }
    lru.push(incomingPage)
}

console.log(memory)
console.log(time)

배열 한 개만 쓰려면, lru 배열만 쓰면 될 것 같다.