반응형
Notice
Recent Posts
Recent Comments
Link
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
Tags more
Archives
Today
Total
관리 메뉴

짧은코딩

LRU(Least Recently Used) 본문

코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)

LRU(Least Recently Used)

5_hyun 2022. 12. 5. 23:29
반응형

LRU

해결 방법

해결 방법으로는 내장 함수를 사용하지 않는 방법과 내장 함수를 사용하는 방법 2가지가 있다.

나는 이 문제를 처음 풀 때 꼼수를 사용하여 맨 뒤부터 불러오는 방식으로 풀려고 했지만 이 방식은 옳은 방법이 아니였다.

 

방법1) 내장 함수를 사용하지 않는 방법

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(size, arr) {
        let answer = Array.from({ length: size }, () => 0);

        arr.forEach((x) => {
          let pos = -1;
          for (let i = 0; i < size; i++) if (answer[i] === x) pos = i;

          if (pos === -1) {
            for (let i = size - 1; i >= 1; i--) {
              answer[i] = answer[i - 1];
            }
          } else {
            for (let i = pos; i >= 1; i--) {
              answer[i] = answer[i - 1];
            }
          }

          answer[0] = x;
        });

        return answer;
      }

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

1. pos는 히트가 되었는지 안되었는지 확인할 수 있는 변수이다. 만약 pos가 -1이면 히트가 되지 않은 것, pos가 -1이 아니면 히트가 된 것이고 pos에 히트 된 위치를 저장한다. 

2. pos가 -1이면 히트가 되지 않았기 때문에 answer에 들어간 모든 값들을 뒤로 한 칸씩 밀어주고 맨 앞에 현재 값을 넣는다.

3. pos가 -1이 아니면 히트가 되었기 때문에 히트 된 앞 부분부터 뒤로 한 칸씩 밀어주고 맨 앞에 현재 값을 넣는다.

 

방법2) 내장 함수를 사용하는 방법

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(size, arr) {
        let answer = Array.from({ length: size }, () => 0);

        arr.forEach((x) => {
          let pos = -1;
          for (let i = 0; i < size; i++) if (answer[i] === x) pos = i;

          if (pos === -1) {
            answer.unshift(x);
            if (answer.length > size) answer.pop();
          } else {
            answer.splice(pos);
            answer.unshift(x);
          }
        });

        return answer;
      }

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

이 방법도 기본은 방법1과 유사하다.

1. pos로 히트가 되었는지 안되었는지 찾는 부분은 똑같다.

2. 만약 pos가 -1이라 히트되지 않았다면 unshift를 통해 answer의 맨 앞에 넣어준다. 만약 answer의 길이가 size보다 커지면 pop을 하여 개수를 유지해준다.

3. 만약 pos가 -1로 히트되었다면 splice를 통해 히트된 위치의 값을 제거해주고 맨 앞에 현재 사용된 값을 넣어준다.

반응형
저작자표시

'코딩테스트 with JS > 자바스크립트 알고리즘 문제풀이(인프런)' 카테고리의 다른 글

뮤직비디오(결정 알고리즘), 이분검색  (0) 2022.12.13
결혼식  (0) 2022.12.11
공주 구하기  (0) 2022.09.09
쇠막대기  (0) 2022.09.08
모든 이나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)  (0) 2022.08.28
'코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)' Related Articles more
Comments