[Algorithm]Sliding Windows

문제

console.log(solution([1, 2, 5, 2, 8, 1, 5], 4)); // 17
console.log(solution([4, 2, 1, 6], 1)); // 6
console.log(solution([4, 2, 1, 6, 2], 4)); // 13
console.log(solution([], 4)); // null

수들의 Array가 있을때, n개의 원소의 합이 최소가 되는 경우를 구하시오

이전 나의 풀이

function solution(array,n){
  let answer=infinity;
  for(let i=0 ;i<array.length;i++){
    for(let j=i+1; j<array.length;j++){
		let sum=array.slice(i,j).reduce((acc,cur)=>acc+cur,0)
        answer=answer>sum?sum:answer;
    }
  }
  return answer;
}

for문 두번에 reduce까지 돌기 때문에 O(n^3)의 시간복잡도를 갖는다.

시간복잡도를 고려한 풀이

function solution(array,n){
  let p1=0;
  let p2=N-1;
  const newArr=[];
  while(p2<arr.length){
    newArr.push(arr.slice(p1,N+p1).reduce((acc,cur)=>acc+cur,0);
    p1++;
    p2++;
  }
  if(newArr.length ===0)return -1;
  return Math.min(...newArr);
}

multiPointer를 사용해서 계산을 해보았지만 그래도 while문 안에 reduce까지 돌아 O(n^2)의 시간복잡도를 가진다.

WindowsSliding

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

1번째부터 N번째까지의 Sum을 만들고 앞으로 한칸sliding 하고 뒤에 원소를 앞으로 하나 땡기는 방식으로 모든 Sum을 확인할 수 있다. 최대 for loop 한번만 돌기 때문에 O(n)의 시간복잡도를 가진다.