leetcode/ 724. Find Pivot Index

Description

Find Pivot Index - LeetCode

Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.

---

Process

인덱스의 왼쪽의 모든 합과 오른쪽의 모든 합이 같은 인덱스를 찾는 문제다.

 

Constraints:

• 1 <= nums.length <= 10^4
• -1000 <= nums[i] <= 1000

nums.length의 범위가 10^4으로 O(n^2)으로 풀면 무리가 있을 수 있겠다.

 

 

---

Solution: Time: 167 ms (35.80%), Space: 15.2 MB (35.92%) 

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        nums_sum = [nums[0]]
        last = len(nums) - 1

        for i in range(1, last + 1):
            nums_sum.append(nums_sum[i - 1] + nums[i])

        if nums_sum[last] - nums_sum[0] == 0:
            return 0
        
        for pivot in range(1, last):
            if nums_sum[pivot - 1] == nums_sum[last] - nums_sum[pivot]:
                return pivot
            
        if nums_sum[last - 1] == 0:
            return last

        return -1

 

1. nums 리스트를 순회하면서 합 배열을 구했다.

2. pivot index == 0인 경우 예외 처리

3. 합 배열을 순회하면서 해당 인덱스의 왼쪽 합과 오른쪽 합이 같은지 비교하고 같다면 해당 인덱스를 반환

4. pivot index == len(nums) - 1인 경우 예외 처리

5. pivot index가 없는 경우 -1 반환

 

---

Enhancement

class Solution(object):
    def pivotIndex(self, nums):
        S = sum(nums)
        leftsum = 0
        for i, x in enumerate(nums):
            if leftsum == (S - leftsum - x):
                return i
            leftsum += x
        return -1

1. nums의 전체합을 구한다

2. 왼쪽의 합을 저장할 leftsum 변수를 0으로 초기화한다

3. nums를 순회하면서 전체합에서 현재 인덱스의 값과 왼쪽의 합을 제외한 값이 왼쪽의 합과 같은지 비교한다

4. 같다면 해당 인덱스를 반환하고 같지 않다면 현재 인덱스의 값을 leftsum에 더해준다

5. pivot index가 없는 경우 -1 반환

---

Conclusion

내가 구현에 약하다는 걸 뼈저리게 느꼈다. 문제를 꼼꼼하게 읽지 않아 첫번째 인덱스와 마지막 인덱스가 pivot 인덱스인 경우를 고려하지 못했었고, 고려했음에도 효율적인 코드를 작성하지 못했다.

문제를 먼저 꼼꼼하게 읽는 습관을 만들고 구현 전에 조금만 더 생각하면서 설계를 할 필요가 있다. 무작정 얕보고 코드부터 작성하는 순간 예외 처리를 충분히 생각하지 못하고 그순간 마음만 급해져서 구현은 더욱 엉망진창이 된다.