슬라이딩 윈도우 - 개념정리

슬라이딩 윈도우

슬라이딩 윈도우는 일정 크기의 윈도우를 옆으로 밀면서 결과값을 도출해야할 때 사용하는 알고리즘이다.

 

백준 21921

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

 

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

---

1

4

2

5

1

 

예를 들어 다음과 같이 방문자 수가 주어지고 X값이 2라면,

2일동안 가장 많이 방문한 방문자 수와 그 기간을 구하는 문제이다.

완전탐색으로 접근을 한다면 다음과 같을 것이다.

 

1 + 4

4 + 2

2 + 5

5 + 1 

 

색칠한 부분의 값들은 중복되어 더해지게 된다.

또한 방문자 수 N만큼 X가 루프문이 돌기 때문에 O(N*X) 만큼의 시간복잡도를 가지게 된다.

슬라이딩 윈도우를 사용하면 O(N)으로 효율성을 높일 수 있다.

 

1

4

2

5

1

1

4

2

5

1

1

4

2

5

1

1

4

2

5

1

 

X가 2이므로 2사이즈의 윈도우를 생성한다.

그리고 이 윈도우를 계속해서 밀면서 배열 끝까지 가면 된다.

이렇게 되면 배열의 사이즈만큼만 실행하게 되므로 시간복잡도를 줄일 수 있게된다.

 

---

 

코드

function solution(x, arr) {
  const tmp = {};
  let windowSum = 0;
  let max = Number.MIN_SAFE_INTEGER;

  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= x - 1) {
      if (tmp[windowSum]) tmp[windowSum]++;
      else {
        tmp[windowSum] = 0;
        tmp[windowSum]++;
      }
      windowSum -= arr[i - (x - 1)];
    }
  }
  console.log(tmp);
  max = Math.max(...Object.keys(tmp).map(Number));
  if (max === 0) {
    console.log('SAD');
  } else {
    console.log(max);
    console.log(tmp[max]);
  }
}

1

4

2

5

1

1

4

2

5

1

 

윈도우를 슬라이딩 할 때, 앞에 있는 수는 빼버리고 그 다음에 오는 수를 추가하는 규칙을 가지고 있다.

즉, 인덱스 기준 arr[2]를 추가한다면 arr[0]은 제거되어야한다. 

이것을 수식으로 정리하면 i - ( k - 1 ) 에 위치하는 값을 빼고 i를 한 칸 옮긴 값을 더해주면 된다.

 

또 다른 규칙은 윈도우 사이즈만큼의 합을 구한 후,

윈도우를 슬라이딩 할 때는 옮기려는 값 - 지우려는 값을 기존의 합에 더해주면 된다.