투 포인터, 슬라이딩 윈도우 (javascript)

투 포인터 & 슬라이딩 윈도우는 언제 사용하는지

배열의 특정 연속된 구간을 처리하기 원하는 경우

• 투 포인터와 슬라이딩 윈도우는 구간을 훑으면서 지나간다는 공통점이 있다.
• 하지만 슬라이딩 윈도우는 구간의 넓이가 동일하다는 점이 차이점이다.

---

투 포인터

1차원 배열에서 배열을 가리키고 있는 2개의 포인터 를 조작하여, 원하는 값을 얻는 알고리즘

예시

• 자연수로 구성된 배열에서 특정한 범위의 합을 구하기
• 합이 9인 부분 연속 수열의 개수를 구하는 경우

코드

function solution() {
  const arr = [1,3,2,2,5,7,2,6];
  const M = 9;
  let ans = 0;
  let start = 0, end = 0, sum = arr[0];
  
  while(arr[start] && arr[end]){
    // M 과 같은 경우
    if(sum === M){
      ans++;
      end++;
      sum += arr[end];
    } 
    // M보다 큰 경우
    else if(sum > M){
      sum -= arr[start];
      start++;
    } 
    // M보다 작은 경우
    else{
      end++;
      sum += arr[end];
    }
  }
  
  return ans;
}

1. 먼저 포인터 2개를 잡는다. (start, end)
2. 처음에 start와 end는 모두 0에서 시작한다.
3. 현재의 sum 의 값과 우리가 찾는 M 값을 비교하여, start와 end의 포인터를 옮겨준다.
4. start, end는 arr index에 존재하는 포인터 값이여야한다.

• start와 M이 같은 경우
  • ans 1 증가하고, end를 한칸 앞으로 이동한다.
  • sum에 end 위치 값을 더해준다.
• 현재 sum의 값이 M 보다 크다면
  • sum에서 현재 start 위치 값을 빼주고 start를 한 칸 앞으로 이동한다.
• sum이 M 보다 작으면
  • end를 한 칸 뒤로 이동하고, sum에 현재 end 위치 값을 더해준다.

---

슬라이딩 윈도우

일정한 사이즈를 가지는 윈도우를 나타낸다. 처음과 끝 포인터가 함께 움직인다.

• 구간이 일정하기 때문에 한 칸씩 앞으로 이동하면 겹치는 영역이 존재하게 된다.
• 따라서 구간의 합이나 구간에서의 최솟값 등을 구할 때 새로 영역으로 들어오는 값과 그 전에 영역에 있었던 값을 체크해주면 된다.

예시

• 고정된 윈도우가 일정한 점위를 유지하면서 이동
• 특정 크기의 부분 배열의 최대 값을 구하는 예제

코드

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

1. 일시적인 합(tempSum) 그리고 가장 큰 합(maxSum), 두개의 변수를 활용
2. 마지막에는 두 값을 비교하여 maxSum을 반환한다.
3. 반복문을 통해 arr[0]부터 시작하여 size의 숫자만큼까지의 배열 값의 총합을 구한다.
4. 두번째 반복문을 통해 범위를 이동시키면서 원래 있던 범위의 뒤에 있는 값을 더하고 맨 앞에 있는 값을 뺀다.

---