LeetCode - 724. Find Pivot Index

https://leetcode.com/problems/find-pivot-index/?envType=study-plan&id=level-1 

Find Pivot Index - LeetCode

 

오답 1

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # needs memoization - with 2 arrays
        sum_upwards = [nums[0]]
        sum_downwards = [nums[len(nums)-1]]

        # (1) sum_upwards
        for i in range(1, len(nums)):
            sum_upwards.append(nums[i]+sum_upwards[i-1])

        # (2) sum_downwards
        for i in range(1, len(nums)):
            sum_downwards.append(nums[len(nums)-1-i]+sum_downwards[i-1])
        sum_downwards.reverse()

        # compare sum_upwards & sum_downwards and find out the pivot value
        print(sum_upwards)
        print(sum_downwards)

        if (0==sum_downwards[1]): # tricky part
            return 0
        if (sum_upwards[len(nums)-2]==0): # tricky part
            return len(nums)-1

        for i in range(1,len(nums)-1):
            if sum_downwards[i+1]==sum_upwards[i-1]:
                return i
        return -1

이렇게 했더니

여기서 에러가 떴다.

 

-> 이 조건을 놓쳤기 때문.

 

다시 작성한 코드는 아래와 같다.

 

 

오답2

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # needs memoization - with 2 arrays
        sum_upwards = [nums[0]]
        sum_downwards = [nums[len(nums)-1]]

        # (1) sum_upwards
        for i in range(1, len(nums)):
            sum_upwards.append(nums[i]+sum_upwards[i-1])

        # (2) sum_downwards
        for i in range(1, len(nums)):
            sum_downwards.append(nums[len(nums)-1-i]+sum_downwards[i-1])
        sum_downwards.reverse()

        # compare sum_upwards & sum_downwards and find out the pivot value

        if (0==sum_downwards[1]): # tricky part
            return 0

        for i in range(1,len(nums)-1):
            if sum_downwards[i+1]==sum_upwards[i-1]:
                return i

        if (sum_upwards[len(nums)-2]==0): # tricky part
            return len(nums)-1

        return -1

이번엔 또 다른 에러가..

흐앗.. 왜 당연히 element 갯수를 3개 이상일꺼라 생각했을까..

다시 수정

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # if array length < 3
        if len(nums)==0:
            return -1
        if len(nums)==1:
            return 0
        if len(nums)==2:
            if nums[0]==0:
                return 1    
            if nums[1]==0:
                return 0
            return -1

        # if array length >=3
        # needs memoization - with 2 arrays
        sum_upwards = [nums[0]]
        sum_downwards = [nums[len(nums)-1]]

        # (1) sum_upwards
        for i in range(1, len(nums)):
            sum_upwards.append(nums[i]+sum_upwards[i-1])

        # (2) sum_downwards
        for i in range(1, len(nums)):
            sum_downwards.append(nums[len(nums)-1-i]+sum_downwards[i-1])
        sum_downwards.reverse()

        # compare sum_upwards & sum_downwards and find out the pivot value

        if (0==sum_downwards[1]): # tricky part
            return 0

        for i in range(1,len(nums)-1):
            if sum_downwards[i+1]==sum_upwards[i-1]:
                return i

        if (sum_upwards[len(nums)-2]==0): # tricky part
            return len(nums)-1
            
        return -1

이렇게 했더니 패스는 되는데...

음.. 뭔가 많이 비효율적으로 짠것같아 보인다... ㅠ

 

 

다른 사람 풀이

그래서 고민하다가 아무리 리팩토링(?)해봐도 수치가 잘 줄지 않길래 다른 사람들이 푼 답안들을 찾아봤다..

https://leetcode.com/problems/find-pivot-index/solutions/3247681/python-solution-o-n-and-o-1-easy-to-understand-with-explanation/

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left =0
        right = sum(nums)
        for index, num in enumerate(nums):
            right-=num
            if left==right:
                return index
            left+=num           
        return -1

헐.. 짧기도 엄청 짧고 확실히 공간복잡도며 시간복잡도며 내꺼보다 훨씬 좋다..

아예 0일때부터 시작해서 빼고 더하기로 쭉 훑으면서 O(n)으로 푸네.. 따로 array두는것도 없고 ㅠ 

 

다른 풀이들 보면 어쨌든 제일 간단하고 효율적인 방법은 요 방법인거같았다..

 

담에 꼭 다시한번 풀어보자...