Running Sum of an Array
정수 배열 nums가 주어집니다. 길이가 같은 새 배열을 반환하세요. 새 배열의 인덱스 i에 있는 요소는 nums[0] + nums[1] + ... + nums[i]이며, 왼쪽부터 처음 i+1개의 숫자를 읽은 뒤의 누적 합입니다.
함수
- numsinteger-array
- 왼쪽에서 오른쪽으로 더할 숫자
- 반환값integer-array
- nums의 각 요소에 대한 누적 합계
제약 조건
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- 모든 누적 합계는 32비트 부호 있는 정수에 들어갑니다.
예제
- 입력
- nums = [3, 1, 4, 1, 5]
- 출력
- [3, 4, 8, 9, 14]
- 설명
- 계속 더합니다:
3, 그다음3 + 1 = 4,4 + 4 = 8,8 + 1 = 9, 그리고9 + 5 = 14. 각 합계는 마지막에 더한 숫자의 인덱스에 저장됩니다.
- 입력
- nums = [-2, 5, -3]
- 출력
- [-2, 3, 0]
- 설명
- 음수는 합계를 낮춥니다:
-2, 그다음-2 + 5 = 3, 그다음3 + (-3) = 0.
- 입력
- nums = [7]
- 출력
- [7]
- 설명
- 숫자 하나에는 그 숫자 자체인 누적 합계가 하나 있으므로, 답은
[7]입니다.
제출 시 숨은 테스트 +13개
후속 질문
각 셀이 왼쪽 위 모서리부터 해당 셀까지 직사각형 영역의 합계를 담는 격자도 똑같이 만들 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
인덱스
i의 답은 인덱스i-1의 답과 어떤 관계가 있나요?두 합은 정확히 하나의 수인
nums[i]만큼 다릅니다. 시작부터 접두 부분의 합을 다시 구할 필요는 없습니다.변수
total하나를 유지하세요.nums를 왼쪽에서 오른쪽으로 순회하며 각 숫자를total에 더하고, 같은 인덱스의 답에total을 기록하세요.
풀이
각 답은 nums의 접두사 합이며, 이웃한 두 접두사는 원소 하나만큼만 차이가 납니다. 각 접두사를 처음부터 다시 계산하면 거의 모든 작업을 반복하게 되지만, 합계를 하나씩 이어서 갱신하면 한 번의 덧셈으로 모든 답을 구할 수 있습니다. 그 결과가 접두사 합 배열이며, 빠른 구간 합을 구할 때 사용하는 도구입니다.
각 접두사의 합을 처음부터 다시 계산하기
핵심 아이디어
정의를 글자 그대로 따르세요. 모든 인덱스 i에 대해 새로운 합계를 0으로 시작하고, nums[0]부터 nums[i]까지 더한 다음 결과를 저장하세요. [3, 1, 4, 1, 5]의 경우 마지막 답은 다섯 숫자를 모두 더합니다. 3 + 1 + 4 + 1 + 5 = 14.
이 방법은 맞지만, 같은 일을 반복합니다. 인덱스 4의 합계는 nums[0]부터 다시 시작합니다. 인덱스 3의 합계인 9에 이미 처음 네 숫자의 합이 들어 있는데도 말이죠. 인덱스 i에는 덧셈이 i+1번 필요하므로, 전체 배열에는 1 + 2 + ... + n = n(n+1)/2번의 덧셈이 필요합니다. n = 5000이면 약 1.25 × 10^7번의 덧셈으로, 5000번이면 충분한 작업입니다.
어차피 반환하는 답 배열을 제외하면, 합계 하나와 인덱스 두 개만 유지하므로 추가 공간은 O(1)입니다.
알고리즘
- 길이가
n인 답 배열을 만듭니다. - 각 인덱스
i에 대해total = 0으로 설정합니다. 0부터i까지의 모든j에 대해nums[j]를total에 더합니다.- 답의 인덱스
i에total을 저장하고, 마지막 인덱스 이후에 답을 반환합니다.
def runningSum(nums):
result = []
for i in range(len(nums)):
total = 0
for j in range(i + 1):
total += nums[j]
result.append(total)
return result누적 합계를 계산하세요
핵심 아이디어
처음 i+1개의 수의 합은 처음 i개의 수의 합에 nums[i]를 더한 값입니다: result[i] = result[i-1] + nums[i]. 따라서 한 단계보다 더 거슬러 올라갈 필요는 없습니다. total 변수 하나만 두고, 각 수를 읽을 때마다 더한 다음 새로운 값을 답에 기록하세요.
[3, 1, 4, 1, 5]에서는 total이 3, 4, 8, 9, 14가 되며, 이 다섯 값이 답입니다. 각 원소는 한 번 읽고 덧셈 한 번만 수행하므로 시간 복잡도는 O(n)입니다. 답 배열을 제외하면 total만 사용하므로 추가 공간은 O(1)입니다.
이 문제에서 어떤 누적 합도 5000 × 10^4 = 5 × 10^7을 넘지 않으므로 32비트 정수에 들어갑니다. 더 큰 입력에서는 누적 합 계산 중 오버플로가 발생하기 쉬우므로 64비트 합계를 사용하는 것이 안전한 기본 선택입니다.
알고리즘
- 길이가
n인 답 배열을 만들고total = 0으로 설정합니다. - 왼쪽에서 오른쪽으로 인덱스를 순회하며
nums[i]를total에 더합니다. - 답 배열의 인덱스
i에total을 씁니다. - 답을 반환합니다.
def runningSum(nums):
result = []
total = 0
for num in nums:
total += num
result.append(total)
return result
함정과 경계 사례
실제로 작업을 하는 줄은 하나뿐이므로, 실수는 합계가 어디에 저장되고 어디로 가는지와 관련이 있습니다.
- 반복문 안에서
total을 초기화하기. 모든 답이nums[i]하나만 남게 되고,[3, 1, 4]는 바뀌지 않은 채 돌아옵니다. i = 0을 처리하지 않고result[i] = result[i-1] + nums[i]를 사용하기. 대부분의 언어에서 인덱스-1은 범위를 벗어나며, Python에서는 마지막 요소를 가리킵니다. 따라서 0부터 시작하는 제자리 버전에서는 마지막 숫자가 첫 번째 숫자에 더해집니다.- 첫 번째 접근법의 내부 반복문을
j < i에서 멈추기.nums[i]가 빠지므로 모든 답이 숫자 하나만큼 부족합니다. - 복사해서 답을 늘리기. R에서
result <- c(result, total)은 매 단계마다 벡터 전체를 복사하므로, 빠른 접근법이 다시 2차 시간이 됩니다. 먼저 전체 길이만큼 메모리를 할당하세요. - C에서
*returnSize = numsSize를 빠뜨리기. 이 값이 없으면 호출한 쪽은 합계를 몇 개 읽어야 하는지 알 수 없습니다.
자주 묻는 질문4
배열의 누적 합이란 무엇인가요?
첫 번째 배열에서 같은 위치까지의 모든 요소를 더한 값이 각 요소인 두 번째 배열입니다. 접두사 합 또는 누적 합이라고도 합니다. [3, 1, 4, 1, 5]의 누적 합은 [3, 4, 8, 9, 14]입니다.
누적 합을 계산하는 시간 복잡도는 얼마인가요?
왼쪽에서 오른쪽으로 합계를 하나씩 누적하면 원소당 한 번씩 덧셈을 하므로 시간은 O(n)이고, 답 외에 추가로 필요한 공간은 O(1)입니다. 각 접두사의 합을 처음부터 다시 계산하면 n(n+1)/2번의 덧셈이 필요하며, 이는 O(n²)입니다.
누적 합계를 제자리에서 계산할 수 있나요?
네. 인덱스 1부터 끝까지 순회하며 nums[i] += nums[i-1]을 설정하세요. 그러면 각 요소에 해당 위치까지의 누적 합이 저장됩니다. nums[i-1]이 이미 그 앞의 모든 값의 합으로 바뀌었기 때문입니다. 입력 배열 외에는 다른 배열을 사용하지 않지만, 원래 값은 사라집니다.
접두사 합은 구간 합 쿼리에 어떻게 도움이 되나요?
누적 합을 구하면 임의의 구간 nums[l..r]의 합은 prefix[r] - prefix[l-1]이며, l = 0인 경우에는 prefix[r]입니다. 누적 합이 [3, 4, 8, 9, 14]일 때 인덱스 2부터 4까지의 합은 14 - 4 = 10입니다. O(n)으로 한 번 순회한 뒤에는 각 쿼리를 O(1) 시간에 처리할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def runningSum(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [3, 1, 4, 1, 5]
기대값
[3, 4, 8, 9, 14]