제시된 합을 가진 부분 배열 찾기

정렬되지 않은 양의 정수로 이루어진 배열 A가 있다. 연속된 원소를 더한 값이 제시된 값 S와 같은 부분 배열을 찾아라. (인덱스 기준은 1이다.)

  • 입력: arr = [1, 2, 3, 7, 5], s = 12, 출력: [2, 4]
    • 인덱스 2부터 4까지의 합: 2 + 3 + 7 = 12
  • 입력: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], s = 15, 출력: [1, 5]

방법

1. 이중 반복문 사용

1
2
3
4
5
6
7
def solution(arr,s):
    for i in range(len(arr)):
        sum = s
        for j in range(i,len(arr)):
            sum -= arr[j]
            if (sum == 0):
                return [i+1,j+1]

2-1. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(arr,s):
    sum = s
    index = 0
    position = 0
    while sum != 0:
        if position == len(arr) - 1:
            return [-1]
        sum -= arr[position]
        if sum < 0:
            index += 1
            position = index
            sum = s
            continue
        position += 1
    return [index+1,position]
  • sum에 s를 할당하여 position 위치의 요소를 하나씩 빼면서 sum 값이 0 보다 작은지 체크
  • 0 보다 작다면 연속되는 부분합이 아니므로 리셋시켜주고 시작 index도 우측으로 이동시킨다.
  • 만약 시작 index가 배열의 끝까지 도달했는데도 sum이 0이 되지 않으면 연속되는 부분합을 만들 수 없다.

2-2. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
def solution(arr,s):
    left,sum = 0,0
    for right in range(len(arr)):
        sum += arr[right]
        while (left < right and sum > s):
            sum -= arr[left]
            left += 1
        if sum == s:
            return [left+1,right+1]
    return [-1]
  • 배열의 첫번째 요소부터 하나씩 sum에 더해준다.
  • sum이 s보다 작거나 같으면 계속 배열의 요소를 더해준다.
  • sum > s를 만족하면, sum에 left 위치의 요소를 빼주면서 sum이 s보다 작거나 같으면 중단
  • 이 때, sum == s를 만족하면 [left+1, right+1]을 반환한다.
  • left == right 일 때, sum == s를 만족하지 않으면 연속되는 부분합이 없다.