[알고리즘] 문제 해결 패턴 (3) 기준점 간 이동 배열 패턴

기준점 간 이동 배열 패턴

배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. 

 

sliding window 접근법

창문을 하나 만들어야 한다. 창문은 단일변수, 하위배열, 또는 필요한 경우 다른 문자열도 될 수 있다. 조건에 따라 창문을 이동시키며, 시작 위치에서 시작하면 보통 왼쪽에서 오른쪽으로 이동한다. 오른쪽에서 왼쪽으로 이동도 가능하고 가운데 위치에서 시작할 수 있다. 그러나 보통 창문을 왼쪽, 즉 요소의 시작 위치 또는 배열이나 문자열의 시작 위치에서 끝나는 위치로 이동한다. 

 

규모가 큰 데이터셋에서 데이터의 하위 집합을 추척하는 문제에 유용하다.

예시 문제

정수의 배열과 n이라는 수를 받아들이는 maxSubarraySum이라는 함수를 작성해라. 이 함수는 배열에서 n개의 연속적인 요소의 최대 합을 계산해야한다. (배열에는 정수만 있으면 된다. 두 번재 숫자를 전달하는 함수는 해당 배열의 연속된 요소의 가장 큰 합계를 계산하면 된다. 2(개)를 전달하면 1이 반환되어야 한다. 8과 2는 연속된 두 숫자 중에서 합계가 가장 크기때문이다. )  

maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null

접근 방법

function maxSubarraySum(arr, num) {
  if ( num > arr.length){
    return null;
  }
  var max = -Infinity;
  for (let i = 0; i < arr.length - num + 1; i ++){
    temp = 0;
    for (let j = 0; j < num; j++){
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  return max;
}

maxSubarraySum([2,6,9,2,1,8,5,6,3],3)

 

시간 복잡도 O(n²)이다.

이 해결책의 안좋은점은 

세가지 항목으로 진행하려면서 합계를 구할때 20개 넘개의 연속된 숫자들 중에서 가장 큰 합계를 찾을 경우에는 비효율적인 방식이다. 

 

리펙토링 

아래의 코드 방법은 슬라이딩 윈도우 방법이다. 

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3);

 

시간 복잡도는 O(n)이므로 루프에서 한번만 빼서 값을 구할 수 있는 장점이다.