15. Find Pivot Index(1991)

문제

https://leetcode.com/explore/learn/card/array-and-string/201/introduction-to-array/1144/

nums라는 array에서 가장 좌측의 pivot index를 구하라.

어떤 인덱스의 좌측 요소의 합과 우측 요소의 합이 같으면 pivot index라고 한다.

0번 인덱스의 좌측 합은 0이고, 가장 마지막 인덱스의 우측 합은 0이라고 가정한다. 

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

 

내가 해결한 방식

좌측 합을 나타내는 left, 

현재 값을 나타내는 current,

우측 합을 나타내는 right,

총 요소 합을 나타내는 total 변수 설정.

 

left는 0에서 시작.

right는 total에서 current를 뺀 값.

left, right 비교 후 일치하지 않으면 다음 인덱스로 넘어감.

넘어가기 전에 left는 현재 값을 더해줌.

total은 right 값으로 치환함. 

i	left	current	right
0	0	1	27
1	1	7	20
2	8	3	17
3	11	6	11

 

time complexity는 O(n) : total을 구할 때 전체 요소를 iterate 함, 최악의 경우 for문에서 전체 요소를 iterate 함. 

def pivotIndex(nums):
    # left는 0에서 시작
    left = 0
    total = sum(nums)

    for i in range(len(nums)):
        current = nums[i]
        right = total - current

        # left, right 비교 후 일치하지 않으면 다음 인덱스로 넘어감.
        if left == right:
            return i
            
        left += current
        total = right

    # pivot index가 없는 경우 -1 반환
    return -1

 

다른 해결 방식(leetcode 솔루션)

내 방식과 비슷하지만 right 변수를 따로 두지 않음.

enumerate를 사용해서 index, current를 동시에 구하고

total에서 left, current를 빼서 right를 구함.

def pivotIndex(nums):
    left = 0
    total = sum(nums)
    
    for index, current in enumerate(nums):
        if left == (total - left - current):
            return index
        left += current
    return -1