코드 리뷰 부탁드립니다

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

function solution(s, arr) {
  const cache = Array.from({ length: s }).fill(0);
  for (let i = 0; i < arr.length; i++) {
    // cache miss
    if (!cache.includes(arr[i])) {
      cache.unshift(arr[i]);
      cache.pop();
    }
    // cache hit
    else {
      const idx = cache.indexOf(arr[i]);
      const temp = cache[idx];
      let j;
      for (j = idx - 1; j >= 0; j--) {
        cache[j + 1] = cache[j];
      }
      cache[j + 1] = temp;
    }
  }
  return cache;
}

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

최악의 경우 O(N^2)인 거 같은데 맞나요 ?

안녕하세요, 인프런 AI 인턴입니다. 박찬욱님의 코드 리뷰 부탁에 대해서 답변해 드리겠습니다.

먼저, 주신 코드는 LRU (Least Recently Used) 캐싱 알고리즘을 구현하는 방식으로 보입니다. LRU 캐싱은 가장 최근에 사용되지 않은 항목을 캐시에서 제거하고, 새로운 항목이나 다시 요청된 항목을 캐시의 앞부분에 추가하는 알고리즘입니다.

예시 코드에서는 cache.includes(arr[i])를 통해서 캐시에 항목이 이미 있는지 확인(cache hit)하고, 없을 경우 새로운 항목을 앞부분에 추가하며 이전 항목을 제거하는 방식(cache miss)으로 처리하고 있습니다. 이미 캐시에 있는 항목을 찾았을 때는 for 루프를 통해 해당 항목을 캐시의 앞부분으로 이동시키는 로직을 처리하고 있습니다.

최악의 경우의 복잡도(O(N^2))에 대한 질문에 대해서는, 내부에 사용된 for 루프와 includes() 메서드 때문에 가능합니다. 각 요소에 대해 ‘cache miss’의 경우 includes()가 최대 O(N)의 시간을, for 루프가 캐시 항목을 이동할 때 최대 O(N)의 시간을 소요할 수 있으므로 여기서 말씀하신 바와 같이 최악의 경우 O(N^2)이 됩니다.

이와 유사한 질문과 답변 케이스를 아래 링크로 확인하실 수 있습니다:
- 삽입정렬 질문입니다! - 삽입 정렬과 관련된 코드 리뷰
- 내장 함수를 사용한 풀이 코드리뷰 부탁드려요 - LRU 캐시 알고리즘을 구현한 코드 리뷰

답변 제공된 링크 중 특히 두 번째 질문 “내장 함수를 사용한 풀이 코드리뷰 부탁드려요“는 LRU 캐시 알고리즘 구현에 관한 것으로, 박찬욱님의 코드와 유사한 문제를 다루고 있으니 참고하시면 도움이 될 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변