프론트엔드 개발자의 기록 공간

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

알고리즘_JS/인프런 JS알고리즘

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

[리우] 2022. 3. 25. 23:56

🚩  LRU 삽입 정렬 응용

 

📖 문제 설명 : 캐시의 개수와 작업의 개수가 주어질 때, LRU 알고리즘과 유사하게 작업을 할 수 있게 구성하면 된다. (자세한 내용은 강의 및 문제지 참고)

 

💡Tip. includes, indexOf 메소드 사용

 

// LRU 삽입 정렬 응용 (카카오 캐시 문제 변형)
// O(n^2)
function solution(S, arr) {
  let answer = [...arr]
  let cache = new Array(S).fill(0)

  answer.forEach((el) => {
    // Cache Miss
    if (!cache.includes(el)) {
      // 한 칸씩 뒤로 미룬 후 처음에 작업 삽입
      for (let i = cache.length - 2; i >= 0; i--) {
        cache[i + 1] = cache[i]
      }
      cache[0] = el
    }
    // Chache Hit
    else {
      let idx = cache.indexOf(el)
      for (let j = idx - 1; j >= 0; j--) {
        cache[j + 1] = cache[j]
      }
      cache[0] = el
    }
  })

  return cache
}

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

 

👨‍💻 코드 설

1. 배열에 해당 요소가 포함되어 있을 경우 Cache Hit, 없을 경우 Cache Miss로 나눈다. 

 

2. Cache Miss일 경우 배열의 요소를 한 칸씩 뒤로 미루고 제일 앞에 해당 요소 삽입

 

3. Cahche Hit일 경우 indexOf로 포함된 문자의 위치를 찾고, 해당 위치에서 제일 앞 요소까지 순회하면서 뒤로 한 칸씩 미룬 뒤, 제일 앞에 해당 요소 삽입

 

* 배열 전체를 순회 화면서 앞으로 미는 작업 대신에 배열 자르기와 shift 연산을 통해 조금 더 깔끔하게도 가능

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.

728x90

'알고리즘_JS > 인프런 JS알고리즘' 카테고리의 다른 글

[이분 탐색] 뮤직비디오  (0) 2022.04.01
[투포인트] 결혼식  (0) 2022.03.26
괄호 문자 제거(스택)  (0) 2022.03.25
모든 아나그램 찾기  (0) 2022.03.25
연속 부분수열 2  (0) 2022.03.16
Comments