Find Pivot Index

Q: Find Pivot Index의 시간 복잡도는 무엇인가요?

전체 합과 누적 합을 사용하는 해법은 O(n) 시간에 실행됩니다. 배열의 값을 더하는 한 번의 순회와 배열을 살펴보는 한 번의 순회가 필요합니다. 추가 공간은 O(1) 만 사용합니다. 반면 각 인덱스에서 양쪽 합을 모두 다시 계산하면 O(n²) 시간이 걸립니다.

Q: 오른쪽 합이 전체 합에서 왼쪽 합과 nums[i]를 뺀 값과 같은 이유는 무엇인가요?

배열의 모든 값은 정확히 세 곳 중 하나에 있습니다. i 의 왼쪽, i 위치 또는 i 의 오른쪽입니다. 각 부분의 합을 더하면 전체 합이 되므로, 오른쪽 합은 전체에서 나머지 두 부분을 뺀 값입니다. 따라서 오른쪽의 값을 전부 더하지 않고도 인덱스를 확인할 수 있습니다.

쉬움누적 합

+10

정수 배열 nums가 주어집니다. 피벗 인덱스란 왼쪽에 있는 값들의 합과 오른쪽에 있는 값들의 합이 같은 인덱스입니다. 피벗 자체의 값은 어느 쪽에도 포함되지 않으며, 값이 없는 쪽의 합은 0입니다.

가장 왼쪽에 있는 피벗 인덱스를 반환하고, 피벗인 인덱스가 없으면 -1을 반환합니다.

함수

pivotIndex(nums: integer-array) → integer

numsinteger-array: 균형을 맞출 정수 배열
반환값integer: 가장 왼쪽 피벗 인덱스, 없으면 -1

제약 조건

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

예제

입력: nums = [3, 1, 5, 2, 2]
출력: 2
설명: 인덱스 2에서 왼쪽은 3 + 1 = 4이고 오른쪽은 2 + 2 = 4입니다. 인덱스 0과 인덱스 1은 균형을 이루지 않으므로(왼쪽 0에 대해 오른쪽 10, 왼쪽 3에 대해 오른쪽 9), 2가 가장 왼쪽에 있는 피벗입니다.

입력: nums = [1, 2, 3]
출력: -1
설명: 세 후보는 각각 5에 대해 0, 3에 대해 1, 0에 대해 3을 줍니다. 균형을 이루는 인덱스가 없으므로 답은 -1입니다.

제출 시 숨은 테스트 +17개

후속 질문

각 값을 한 번씩만 읽고 먼저 전체 합을 구하지 않으면서 가장 왼쪽 피벗을 찾을 수 있나요? 메모리는 얼마나 사용하나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

인덱스 하나를 확인하는 데는 두 번의 합산이 필요하지만, 모든 인덱스에서 합을 다시 계산하면 작업량은 길이의 제곱에 비례해 증가합니다. 해결 방법은 합을 다시 계산하지 않는 것입니다. 왼쪽 합은 단계마다 값 하나씩 더해지고, 오른쪽 합은 전체 합에서 남은 값입니다. 전체 합을 구하는 한 번의 순회와 누적 왼쪽 합을 사용하는 두 번째 순회로, 두 개의 숫자만 메모리에 저장한 채 가장 왼쪽의 피벗을 찾을 수 있습니다.

모든 인덱스에서 양쪽 값을 더하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

정의에 따르세요. 각 인덱스 i에 대해 그 앞의 값들을 모두 더하고, 그 뒤의 값들을 모두 더한 다음 비교하세요. 인덱스를 왼쪽에서 오른쪽으로 확인하므로 두 합이 일치하는 첫 번째 인덱스가 정답입니다.

양 끝은 저절로 처리됩니다. 인덱스 0에서는 왼쪽 반복문이 0회 실행되므로 왼쪽 합은 0입니다. 마지막 인덱스에서는 오른쪽 반복문이 0회 실행됩니다. 그래서 [4, -4, 9]는 2를 반환합니다.

문제는 비용입니다. 각 인덱스에서 나머지 n-1개의 값을 모두 더하므로, 전체 작업량은 덧셈 약 n²회입니다. 값이 10,000개라면 덧셈이 거의 1억 회에 이르고, 대부분은 바로 앞 인덱스에서 이미 계산한 합을 반복하는 것입니다.

알고리즘

nums의 모든 인덱스에 대해 i를 반복합니다.
왼쪽 합으로 nums[0]부터 nums[i-1]까지 더합니다.
오른쪽 합으로 nums[i+1]부터 마지막 값까지 더합니다.
두 합이 같으면 i를 반환합니다.
일치하는 인덱스가 없으면 -1을 반환합니다.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

누적 합 배열

핵심 아이디어

브루트 포스 방식은 배열의 값들을 계속 더해 나갑니다. 접두사 합 배열을 사용하면 이 작업을 한 번만 수행하면 됩니다. prefix[k]를 처음 k개 값의 합이라고 하고, prefix[0] = 0으로 둡니다. [3, 1, 5, 2, 2]의 경우 [0, 3, 4, 9, 11, 13]이 됩니다.

이제 어떤 구간의 합이든 두 항목의 차이로 구할 수 있습니다. 인덱스 i의 왼쪽은 처음 i개의 값이므로 prefix[i]입니다. 오른쪽은 nums[i] 뒤에 있는 모든 값이며, 이는 prefix[n] - prefix[i+1]입니다. 인덱스 2에서는 왼쪽이 4이고 오른쪽은 13 - 9 = 4이므로, 피벗입니다.

배열을 만드는 데 한 번 순회하고 각 확인은 상수 시간이 걸리므로, 전체 탐색은 O(n)입니다. 대신 메모리에 n+1개의 숫자를 추가로 저장해야 합니다.

알고리즘

길이가 n+1인 prefix를 만들고 prefix[0] = 0으로 설정합니다.
값을 채웁니다: prefix[k+1] = prefix[k] + nums[k].
각 인덱스 i에 대해 왼쪽 합은 prefix[i]로, 오른쪽 합은 prefix[n] - prefix[i+1]로 읽습니다.
두 합이 같은 첫 번째 i를 반환하고, 그런 값이 없으면 반복문이 끝난 뒤 -1을 반환합니다.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

전체 합계와 누적 왼쪽 합계

핵심 아이디어

이전 접근 방식이 어떤 접두사 항목을 읽는지 살펴보세요. 인덱스 i에서는 prefix[i], prefix[i+1], prefix[n]이 필요합니다. 마지막 항목은 변하지 않는 전체 합이고, 나머지 두 항목은 배열을 한 번 순회했을 때의 누적 합입니다. 따라서 전체 배열을 저장하는 대신 전체 합과 왼쪽 누적 합 하나를 유지하면 됩니다.

모든 값은 왼쪽, 피벗 또는 오른쪽에 있습니다. 따라서 오른쪽 합은 전체 합에서 왼쪽 합과 nums[i]를 뺀 값입니다. [3, 1, 5, 2, 2]의 전체 합은 13입니다. 인덱스 0에서 왼쪽 합은 0이고 오른쪽 합은 13 - 0 - 3 = 10입니다. 인덱스 1에서는 왼쪽 합이 3이고 오른쪽 합이 9입니다. 인덱스 2에서는 왼쪽 합이 4이고 오른쪽 합은 13 - 4 - 5 = 4이므로 2를 반환합니다.

루프 안의 순서가 중요합니다. 먼저 비교한 다음 nums[i]를 왼쪽 합에 더해야 인덱스에서 검사 중인 값이 왼쪽 합에 포함되지 않습니다. 첫 번째 일치 항목에서 반환하면 가장 왼쪽에 있는 피벗을 찾을 수 있습니다.

배열을 전체 합 계산과 탐색에 한 번씩, 총 두 번 읽으므로 시간 복잡도는 O(n)입니다. 숫자 두 개만 저장하므로 추가 공간 복잡도는 O(1)입니다.

알고리즘

모든 값을 total에 더합니다.
left를 0으로 설정합니다.
각 인덱스 i에 대해 left가 total - left - nums[i]와 같으면 i를 반환합니다.
그렇지 않으면 nums[i]를 left에 더하고 다음으로 넘어갑니다.
루프가 끝나면 -1을 반환합니다.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

함정과 경계 사례

대부분의 오답은 피벗 자체의 값을 한쪽에 포함하거나 가장자리 인덱스를 건너뜁니다.

비교하기 전에 왼쪽 합에 nums[i]를 더하는 경우. 그러면 왼쪽에 피벗 값이 포함되어 [3, 1, 5, 2, 2]에서 더 이상 인덱스 2를 찾지 못합니다.
오른쪽 합을 total - left로 계산하는 경우. 그러면 오른쪽에 nums[i]가 포함되므로 이것도 빼야 합니다.
인덱스 0이나 마지막 인덱스를 건너뛰는 경우. 빈 쪽의 합은 0이므로 두 인덱스 모두 피벗일 수 있습니다. [1, -1, 1]은 0을 반환하고 [4, -4, 9]는 2를 반환합니다.
첫 번째 일치 항목 대신 마지막 일치 항목을 반환하는 경우. [0, 0, 0]에서는 모든 인덱스의 균형이 맞으며, 답은 0입니다.
양쪽 끝에서 안쪽으로 이동하며 더 작은 쪽을 키우는 투 포인터를 사용하는 경우. 이 방법은 모든 값이 음수가 아닐 때만 작동합니다. 여기서는 값이 -1000까지 내려가므로, 한쪽은 커지면서 합이 줄어들 수도 있습니다.
Lua와 R 배열이 1부터 시작한다는 점을 잊는 경우. 답을 0부터 시작하는 인덱스로 만들려면 i-1을 반환하세요.

자주 묻는 질문4

Find Pivot Index의 시간 복잡도는 무엇인가요?

전체 합과 누적 합을 사용하는 해법은 O(n) 시간에 실행됩니다. 배열의 값을 더하는 한 번의 순회와 배열을 살펴보는 한 번의 순회가 필요합니다. 추가 공간은 O(1)만 사용합니다. 반면 각 인덱스에서 양쪽 합을 모두 다시 계산하면 O(n²) 시간이 걸립니다.

오른쪽 합이 전체 합에서 왼쪽 합과 nums[i]를 뺀 값과 같은 이유는 무엇인가요?

배열의 모든 값은 정확히 세 곳 중 하나에 있습니다. i의 왼쪽, i 위치 또는 i의 오른쪽입니다. 각 부분의 합을 더하면 전체 합이 되므로, 오른쪽 합은 전체에서 나머지 두 부분을 뺀 값입니다. 따라서 오른쪽의 값을 전부 더하지 않고도 인덱스를 확인할 수 있습니다.

두 포인터로 피벗 인덱스 찾기 문제를 풀 수 있을까요?

확실하게 그렇지는 않습니다. 항상 더 작은 쪽을 확장하는 투 포인터 탐색은 값을 더하면 한쪽이 커진다고 가정하지만, 값이 음수일 수 있으면 이 가정은 성립하지 않습니다. 쪽을 확장하는 동안 오히려 크기가 줄어들 수 있으므로, 탐색에서 포인터가 실제 피벗을 지나칠 수 있습니다. 누적 합 방식은 부호에 대해 어떤 가정도 하지 않고 모든 인덱스를 확인합니다.

원소가 하나인 배열의 피벗 인덱스는 무엇인가요?

0입니다. 유일한 요소의 양쪽은 모두 비어 있고, 빈 쪽의 합은 0이므로 양쪽의 합은 같습니다. 누적 합을 사용하는 풀이에서는 첫 번째 비교에서 0을 반환합니다. 왼쪽 합은 0이고, 전체 합에서 0과 해당 값을 빼도 역시 0입니다.

Python

def pivotIndex(nums):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [3, 1, 5, 2, 2]

기대값

Find Pivot Index

함수

제약 조건

예제

힌트

풀이

모든 인덱스에서 양쪽 값을 더하세요

누적 합 배열

전체 합계와 누적 왼쪽 합계

함정과 경계 사례

자주 묻는 질문4

비슷한 문제