[JS] 코딩 테스트 문제 : 연속부분수열1

문제 : 연속부분수열1

문제 설명

N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

▣ 입력설명

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.

▣ 출력설명

첫째 줄에 경우의 수를 출력한다.

▣ 입력예제 1

8 6
1 2 1 3 1 1 1 2

▣ 출력예제 1

3

내코드

  function solution(m, arr) {
    let answer = 0,
      sum = 0;
    let answerArr = [];

    // 배열 만큼 순회
    arr.forEach((element, index, array) => {
      let tmpArr = [];
      sum += element;
      tmpArr.push(element);

      // index 번째 부터 배열의 마지막까지 순회 (현재 숫자부터 연속된 수열을 찾음)
      // 숫자 합이 m 같아질때 결과 배열에 저장 m 보다 커지면 정지 
      for (let i = index + 1; i < array.length; i++) {
        if (sum + array[i] > m) {
          break;
        } else {
          sum += array[i];
          tmpArr.push(array[i]);
        }

        if (sum === m) {
          answerArr.push([...tmpArr]);
          answer++;
          break;
        }
      }
      sum = 0;
      tmpArr = [];
    });


    console.log(answerArr);
    return answer;
  }

  let a = [1, 2, 1, 3, 1, 1, 1, 2];
  console.log(solution(6, a)); // 3
  // answerArr : [[2, 1, 3],[1, 3, 1, 1],[3, 1, 1, 1]]

풀이

1. 배열을 순회하면서 현재 숫자부터 배열의 마지막까지 다시 순회하면서 임시로 배열에 저장하고 값들의 합 또한 저장한다.
2. 숫자 합이 m 보다 커지면 정지, 작으면 계속 진행 m 과 같아질 때의 경우를 저장

다른 해결 방법

  function solution(m, arr) {
    let answer = 0,
      lt = 0,
      sum = 0;
    let answerArr = [];
    for (let rt = 0; rt < arr.length; rt++) {
      sum += arr[rt];
      if (sum === m) {
        answer++;
        answerArr.push(arr.slice(lt, rt + 1));
      }
      while (sum >= m) {
        sum -= arr[lt++];
        if (sum === m) {
          answer++;
          answerArr.push(arr.slice(lt, rt + 1));
        }
      }
    }
    console.log(answerArr);
    return answer;
  }

1. 연속된 값의 처음과 끝 인덱스를 저장할 두 포인터를 생성
2. 0 부터 배열의 수만큼 반복문을 실행(rt: 연속된 값의 끝 인덱스 의미하게 된다) 그 안에서 값의 합이 m 을 넘지 않으면 계속, m과 값이 같아지는 경우는 저장한다
3. m 보다 커지는 경우 기존에 0 이었던 포인트 (lt: 연속된 값의 처음 인덱스 의미하게 된다) 즉 배열의 0번 째 값을 빼고 포인트를 1 증가시키고 결과의 합을 다시 비교한다

m 값에 맞게 연속된 값의 처음과 끝 인덱스를 조정하는 투포인트 알고리즘으로 최소한의 동작으로 원하는 연속부분수열을 얻을 수 있다.

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard