Least Recently Used(카카오 캐시 문제 변형)

문제

캐시 크기(5)가 정해지고 배열값이 들어올때 최종 작업차례를 출력하는 프로그램 작성하시오.

1) Cache Miss: 
2 3 1 6 7 에서 5번이 들어오면 맨뒤의 7이 밀려서 삭제. 
최종 5 2 3 1 6 이됨

2) Cache Hit:
5 2 3 1 6 에서 3번이 들어오면, 3이 이미 있기 때문에 맨 앞으로 나옴.
최종 3 5 2 1 6 이됨

입력예제 1
5(캐시크기) 9(배열크기)
1 2 3 2 6 2 3 5 7

출력예제 1
7 5 3 2 6

 

 

 

풀이

내장함수 사용 안한걸 기준.

1. size만큼의 0을 채워서 answer 배열 생성

2. arr(작업)을 forEach를 돌린다.

3. size만큼 반복문을 돌리며 answer안에 arr의 요소(x)가 있는지 확인. 있다면 pos 변수에 index 담음.

4. pos가 -1이면 answer에 arr의 요소(x)가 없다는 소리이므로,  맨앞의 요소를 한칸씩 뒤로 움직임. 맨 앞 요소에 x값삽입

5. pos가 -1이 아니면, answer에 arr의 요소(x)가 있다는 의미 이므로, pos번자리부터 1번 자리까지 오른쪽으로 한 칸씩 뒤로 움직임. 맨 앞 요소에 x값 삽입

6. answer 리턴

 

코드

// 내장함수 사용 X - 할줄 알아야함.
function solution(size, arr){
  let answer=Array.from({length: size}, () => 0); // 1
  arr.forEach(x => {  // 2
    let pos=-1;
    for (let i = 0; i < size; i++) if (answer[i]===x) pos = i; // 3

    if (pos === -1) {  // 4
      for (let i = size-1; i > 0; i--) {
        answer[i] = answer[i-1];
      }
    } else {  // 5
      for (let i = pos; i > 0; i--) {
        answer[i] = answer[i-1];
      }
    }
    answer[0] = x;
  })
  return answer;  // 6
}

let arr=[1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr)); //(5) [7, 5, 3, 2, 6]

---

//내장함수 사용
function solution(size, arr){
  let answer=Array(size).fill(0);
  for (let x of arr){
    let find = answer.indexOf(x);
    
    if (find < 0) {
      answer.unshift(x);
      if (answer.length > size) answer.pop();
    }
    else{
      answer.splice(find, 1);
      answer.unshift(x);
    }
  }
  return answer;
}

let arr=[1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr)); //(5) [7, 5, 3, 2, 6]

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의