연속 부분수열 2

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

 

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

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

 

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

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

 

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

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

 

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

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

  for (let lt = 0; lt < arr.length; lt++) {
    rt = lt
    sum = arr[rt++]

    while (sum <= m && rt <= arr.length) {
      result += 1
      sum += arr[rt++]
    }
  }
  return result
}

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

 

👨‍💻 코드 설명

연속 부분 수열1 문제와 유사하다. 다만 여기서는 연속된 배열에서 특정 숫자 M 이하의 경우를 구해야 하므로 로직은 다음과 같이 구성할 수 있다.

 

1. 반복문을 통해 배열 처음부터 끝까지 순회한다.

 

2. 시작 시점을 sum으로 초기화 후 while을 통해 rt 변수를 오른쪽으로 옮겨가면서 M보다 작을 때까지 

계속 더해나가고 개수(result)도 카운트해준다.

 

3. 만약 sum이 M보다 클 경우 연속된 배열에서 M 이하인 경우의 수가 끝났으므로 다음 반복문을 수행한다.

 

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