선입선출 알고리즘 (JS)

선입선출(FIFO)알고리즘은 가장 먼저 들어와서 가장 오래있었던 페이지를 우선으로 교체 시키는 방법을 의미한다. 

hit일땐 실행시간이 1초, miss일때의 실행시간은 6초이다. 전체의 실행시간을 자바스크립트 코드로 구해보자. 

문제보기

테스트케이스 

페이지	페이지 프레임	실행시간
BCBAEBCE	3	38
ABCABCABC	3	24
ABCDABEABCDE	4	62
ABCEDF	0	36
ABCDABEA	3	43

 

---

내가 푼 코드이다. 

function solution(pageFrame, page) {
  let memory = [];
  let result = 0;

  for (let key of page) {
    let check = false;

    // 1. 메모리안에 포함되어있으면 히트이면서 메모안에 없을떄만 push 
    if (memory.includes(key)) {
      check = true;
    } else {
      memory.push(key);
    }

    // 2. 메모리의 크기가 페이지프레임보다 크면 맨앞에서 가장 먼저 들어온 값을 삭제 
    if (memory.length > pageFrame) {
      memory.shift();
    }

    if (check) {
      result += 1;
    } else {
      result += 6;
    }
  }
  return result;
}

let page = 'BCBAEBCE';
let pageFrame = 3;
console.log(solution(pageFrame, page));

[ 설명 ]

function으로 페이지프레임과 페이지를 받는다. memory를 선언한다. 이 메모리에는 페이지의 입력 순서대로 담길것 이며, 페이지프레임의 크기를 넘지 않는다. 

for of 문으로 page에 담긴 문자열을 차례차례 순회하여 메모리에 담는다. 이때 이미 메모리 안에 해당값이 있다면 hit임으로  +1초이고 아닐경우에는 +6초이다. FIFO입으로 메모리의 크기가 페이지 프레임보다 크면 맨앞에서 가장 먼저들어온 값을 shift한다. 

 

[ 답안 ]

// 선입선출 알고리즘 

function solution(frame, page) {
  let runTime = 0;
  let temp = [];

  // frame 0일떄 page의 크기만큼 6을 곱해주고 끝낸다.
  if (frame === 0) {
    runTime = page.length * 6;
    return runTime;
  }

  for (let i of page) {
    if (temp.includes(i)) {
      runTime += 1
    } else {
      // 배열이 비었으면 무조건 넣어준다.
      if (temp.length < frame) {
        temp.push(i);
      } else {
        // 가장 사용되지 않은 첫번째 배열을 제거하고 맨 뒤에서 입력값을 넣어준다.
        temp.shift();
        temp.push(i);
      }
      // if문의 실행에 상관없이 runTime은 10이 추가된다. 
      runTime += 6;
    }
  }
  return runTime;
}

const frame = 3;
const page = 'BCBAEBCE'.split('');
console.log(solution(frame, page));