[Python] Leetcode 724. Find Pivot Index (Easy)

https://leetcode.com/problems/find-pivot-index/

Find Pivot Index - LeetCode

 

좌측합과 우측합을 같게 만드는 중심을 찾는 꽤 재밌는 문제였습니다.

 

슬라이딩 윈도우와 비슷한 느낌으로 구현했는데, 좌측합이 0, 우측합이 모든 누적합인 상태로 시작해서 이번 턴에 중심으로 테스트하는 값을 우측합에서 빼고 이전 턴에 테스트한 값을 좌측합에 더하는 식으로 구현했습니다.

 

testcase 1번값의 풀이진행을 그림으로 나타내면 아래와 같습니다.

 

 

class Solution:
    # def pivotIndex(self, nums: List[int]) -> int:
    def pivotIndex(self, nums: list) -> int:
        pivot = -1
        idx = 0
        leftSum = 0
        rightSum = self.getRightSum(nums)

        while(idx < len(nums)):
            rightSum -= nums[idx]
            if(idx > 0):
                leftSum += nums[idx-1]
            
            if(leftSum == rightSum):
                pivot = idx
                break
            idx += 1

        return pivot
    
    def getRightSum(self, nums:list):
        rightSum = 0
        for i in nums:
            rightSum += i

        return rightSum


input = [[1,7,3,6,5,6],[1,2,3],[2,1,-1]]
for i in input:
    print(Solution().pivotIndex(i))