[알고리즘JS] 연속 부분 수열 합의 개수 (프로그래머스 lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

풀이

• 슬라이딩 윈도우와 Set 객체를 활용한 풀이
• 슬라이딩 윈도우는 아래와 같이 지정된 범위를 가지고  한 칸씩 움직이는 풀이 방법이다. 하나의 반복에서 다음 범위로 넘어가기 위해 맨 앞 요소를 빼고 맨 뒤 요소를 더한다.

function solution(elements) {
  const set = new Set();
  const N = elements.length;

  // 1 ~ n 길이까지의 연속부분수열을 만들기 위해 전체 길이만큼 반복
  for (let len = 1; len <= N; len++) {
    let rear = 0;
    let sum = 0;

    for (let front = 0; front < N; front++) {
      // 각 반복이 시작되면 윈도우 범위만큼 sum을 만들어둠
      if (front === 0) {
        while (rear < len) {
          sum += elements[rear++];
        }
      }
      // 그 이외의 경우 윈도우 범위에서 하나씩 더하고 빼면서 연속 부분수열의 합을 만든다.
      else {
        // front 이전 값을 뺀다.
        sum -= elements[front - 1];
        // rear가 전체 배열의 끝에 다다르면, 다시 앞으로 돌아간다.(순환)
        if (rear === N) rear = 0;
        // rear 값을 더한다.
        sum += elements[rear++];
        
        // sum += elements[(j+i-1) % len]; => 나눈 나머지로 rear를 구하는 법도 있음.
      }
      set.add(sum);
    }
  }

  return set.size;
}

• 이 범위의 시작점을 front, 끝지점을 rear 라는 변수로 선언했다.
• 연속된 부분 수열은 길이가 1부터 2, 3, ... 전체 배열의 길이가 되므로, elements 의 길이만큼 반복문을 돌려 len 을 구했다.
• 그리고 front 와 rear를 오른쪽으로 한 칸씩 이동하며 len 범위만큼의 부분 수열 합을 구할 것이기 때문에, rear, sum 을 0으로 초기화한다.
• front 가 0인 경우 다음 길이의 연속 부분 수열을 구한다는 의미이므로, front, rear 를 하나씩 더하고 빼면서 구해줄 고정된 window (sum) 을 먼저 구해준다. 
• front 의 다음 반복부터 sum 에서 front - 1 을 빼고 rear 를 더해준다. 
• 순환 구조로 이루어졌기 때문에 rear 가 전체 배열의 길이에 다다르면 다시 0으로 초기화해준다.