특정한 합을 가지는 부분 연속 수열 찾기

[hsskey]

특정한 합을 가지는 부분 연속 수열 찾기

• N = 8개의 자연수로 구성된 수열이 있다. (데이터의 개수)
• 합이 M = 5인 부분 연속 수열의 개수를 구하여라 (부분합)

📝 제약조건

• 수행 시간 제한은 O(N)이다.

💡 예시

• Input: n = 8, m = 5, data = [3, 2, 4, 1, 2, 2, 1, 5]
  • Output: 5

문제 해결 과정

Step 1: 문제 이해하기

• 수열 data에서 연속된 부분 수열의 합이 m과 같은 경우의 수를 찾아야 합니다.
• 수열의 길이 n은 최대 8이며, 문제는 시간 복잡도 O(N)으로 해결해야 합니다.
• 연속된 부분 수열이기 때문에 start와 end 포인터를 활용하는 투 포인터 알고리즘을 고려할 수 있습니다.

Step 2: 접근 방법

• 배열을 선형적으로 탐색하는 문제 -> 투포인터 떠올리기(시작점과 끝점 설정해서 데이터의 범위를 표현)
• 투 포인터 알고리즘 활용:
  • 두 개의 포인터(start, end)를 사용하여 연속된 부분 수열의 합을 계산하는 투 포인터 방식을 사용합니다.
  • start를 차례로 이동시키며 end를 확장하는 방식으로 부분합을 구합니다.
  • 부분합이 목표값 m보다 작으면 end를 오른쪽으로 확장해 수열의 길이를 늘리고, 부분합이 m에 도달하면 카운트를 증가시킵니다.
  • 부분합이 목표값을 초과하면 start를 이동시켜 수열을 축소합니다.

Step 3: 코드 설계

n = 배열의 길이
m = 목표 부분합
data = 수열

cnt = 0
intervalSum = 0
end = 0

for start = 0 to n - 1:
    while (intervalSum < m) and (end < n):
        intervalSum += data[end]
        end += 1

    if intervalSum

Step 4: 코드 구현

• 설계한 알고리즘에 따라 코드를 작성하고 테스트합니다.

let n = 8 // 데이터의 개수 N
let m = 5 // 찾고자 하는 부분합(target)
let data = [3, 2, 4, 1, 2, 2, 1, 5] // 전체 수열

let cnt = 0
let intervalSum = 0 // 부분합 저장
let end = 0

// start를 고정시킨 상태에서 end를 최대한 오른쪽으로 이동시키는 방식!
for (let start = 0; start < n; start++) {
    // end를 가능한 만큼 이동시키기(합이 m이상이 될 때 멈출수 있도록 처리)
    while(intervalSum < m && end < n) {
        intervalSum += data[end]
        end += 1
    }
    // 부분합이 m일때 카운트 증가
    if(intervalSum == m) cnt += 1
    intervalSum -= data[start]
}

console.log(cnt)

[hsskey]

수들의 합 2와 동일 ex) i부터 j까지의 합 -> 구간합 (특정한 합을 가지는 부분연속수열의 갯수)