🎯 슬라이딩 윈도우

만약 [1, 2, 3, 4, 5, 6, 7]로 이루어진 배열에서 연속적인 3개의 숫자의 합의 최댓값을 구하는 문제를 마주했다고 가정해보자. 만약 반복문을 통해서 처음 3개, 그 다음 3개, 그 다음 3개… 이렇게 계속 구하다보면 시간초과가 발생할 가능성이 높다.

이럴 때 슬라이딩 윈도우 알고리즘을 사용한다.

  • 먼저 처음 배열 [1, 2, 3]의 합을 구한다.
  • 다음 배열 [2, 3, 4]를 구하는데 [1, 2, 3] 배열에서 맨 앞의 값이 빠지고, 그다음 값인 4가 들어온 모습이다.
  • 이러한 규칙을 바탕으로 다음 배열의 값은 전 배열에서 처음 원소를 빼고 다음에 들어올 원소를 더해주면 된다.

결과적으로 슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 의미한다.

🎯 코드 구현 (JS)

👉 문제 확인하기 : BOJ - DNA 비밀번호

const fs = require('fs');
const input = fs.readFileSync('example.txt').toString().trim().split('\n');

const [N, P] = input.shift().split(' ').map(Number);
const stringArr = input.shift();

const [A, C, G, T] = input.shift().split(' ').map(Number);

let answer = 0;
let countDNA = [0, 0, 0, 0];

// 초기 윈도우 설정
for (let i = 0; i < P; i++) {
  if (stringArr[i] === 'A') countDNA[0]++;
  else if (stringArr[i] === 'C') countDNA[1]++;
  else if (stringArr[i] === 'G') countDNA[2]++;
  else if (stringArr[i] === 'T') countDNA[3]++;
}

// 초기 윈도우에 대한 검사
if (countDNA[0] >= A && countDNA[1] >= C && countDNA[2] >= G && countDNA[3] >= T) answer++;

// 슬라이딩 윈도우로 나머지 부분 탐색
for (let i = P; i < N; i++) {
  // 이전 윈도우의 첫 번째 문자 제거
  if (stringArr[i - P] === 'A') countDNA[0]--;
  else if (stringArr[i - P] === 'C') countDNA[1]--;
  else if (stringArr[i - P] === 'G') countDNA[2]--;
  else if (stringArr[i - P] === 'T') countDNA[3]--;

  // 새로운 문자 추가
  if (stringArr[i] === 'A') countDNA[0]++;
  else if (stringArr[i] === 'C') countDNA[1]++;
  else if (stringArr[i] === 'G') countDNA[2]++;
  else if (stringArr[i] === 'T') countDNA[3]++;

  // 윈도우 내의 문자들이 조건을 만족하는지 확인
  if (countDNA[0] >= A && countDNA[1] >= C && countDNA[2] >= G && countDNA[3] >= T) answer++;
}

console.log(answer);