연속 부분수열 1

🚩  연속 부분 수열 1 -> 투포인터 알고리즘

 

📖 문제 설명 : 여러 개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속 부분 수열의 합이 특정 숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을
작성하세요.
만약 M=6이고 수열이 다음과 같다면 [1, 2, 1, 3, 1, 1, 1, 2]
합이 6이 되는 연속 부분 수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

 

input : M = 6 , arr = [1, 2, 1, 3, 1, 1, 1, 2] => output : 3

input : M = 6 , arr = [1, 1, 1, 2, 4] => output : 1

 

💡Tip. 투포인터 알고리즘으로 이중 for 문으로 전체 탐색을 하면 O(n^2)이 되기 때문에

투포인터 알고리즘을 이용하여 O(n)으로 해결해야 한다.

 

👉 소스 코드  ⏰시간복잡도 O(n)

function solution(arr, m) {
  let result = 0,
    lt = 0,
    sum = 0

  for (let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt]
    if (sum === m) result += 1

    while (sum >= m) {
      sum -= arr[lt++]
      if (sum === m) result += 1
    }
  }
  return result
}

for 문안에 있는 while 문의 총 반복 횟수가 n을 넘지 않기 때문에 시간 복잡도는 O(n)이다.

 

 

👨‍💻 코드 설명

"연속된 ~~를 구해라"  문제에서 "연속된" 키워드가 있고 흔히 생각했을 때,

이중 반복문으로 해결할 수 있는 경우는 투포인트 알고리즘이다.

 

1. 배열의 위치를 기억하는 두 개의 변수를 이용한다. (left, right)

처음부터 배열 끝까지 반복을 수행하는 right 변수,

누적 합이 주어진 M보다 클 때, 배열의 제일 앞 부분에 있는 요소를 제거하면서 M보다 작게 만들어야 하므로 이를 기억하는 left 변수를 이용한다.

 

2. 반복문을 통해 배열의 요소의 누적 합을 구한다.

 

3. 만약 누적 합이 M과 같다면 개수를 카운트해준다.

 

4. 만약 누적 합이 M 이상이라면 3번에서 카운트를 해줬기 때문에 연속된 배열의 위치를 수정한다.

 4-1. left 변수를 옮기면서 누적 합이 M보다 작을 때까지 배열의 left가 가리키고 있는 요소를 빼준다.

 4-2. 만약 누적 합이 M과 같다면 개수를 카운트해준다.

 

즉, 배열에서 왼쪽, 오른쪽 두 개의 변수를 이용하여 연속된 길이에서의 누적합을 통해 M과 같을 때를 구해주면 된다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.