오늘의 리트코드 (1)

'''
Q. Running Sum of 1d Array 1480

nums라는 배열이 주어져있을때, 우리는 다음과 같은 형식의 배열을 리턴해야한다.
runniongSum[0] = nums[0]
runniongSum[1] = nums[0] + nums[1]
runniongSum[2] = nums[0] + nums[1] + nums[2]

runniongSum[n] 의 갑은 nums[0] .. nums[n] 까지의 합과 같다.

sum 함수는 너무 많은 메모리를 사용할 수 있으니 되도록이면 피하자.
이전항의 크기는 이전항까지의 합을 모두 담고 있다는 점을 이용해서 구현해보자.
'''


def runningSum(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """

    for i in range(0,len(nums)):
        if i == 0:
            nums[i] = nums[i]
        else :
            nums[i] = nums[i-1] + nums[i]

    print(nums)



if __name__ == '__main__':
    nums = [1, 2, 3, 4]
    runningSum(nums)

'''
Q. find pivot index 724
정수배열인 nums가 주어졌을 때 해당 배열의 pivot의 index를 구하는 것이 목표.
pivot을 정하는 기준은 left,right로 나누어서 양 쪽의 합이 같아지는 지점
단,pivot을 제외하고 계산함.

left sum = 0 일 경우도 계산해야함 -> 까다로울수도


'''


def pivotIndex(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    for pivot in range(0,len(nums)):
            left = nums[:pivot]
            right = nums[pivot+1:]

            left_sum = sum(left)
            right_sum = sum(right)

            if left_sum == right_sum:
                return pivot

        return -1



if __name__ == '__main__':
    nums = [1, 7, 3, 6, 5, 6]
    nums2 = [2,1,-1]

    print(pivotIndex(nums2))

처음에 풀었던 풀이.
효율성이 매우 낮고 부끄러운 코드다.아무리 생각해봐도 sum을 이렇게 남발하면 난리가 날 것 같다고 생각해서 다른 코드를 찾아보다가 아래의 방식으로 구현할 수 있다는 것을 알아냇다.

인덱스를 이용하여 미리 pivot을 빼준다.
pivot을 미리 빼놓은 값과 아직, left sum 값을 새로 할당하기 전의 값을 비교하기 때문에 걱정했던 3번 케이스도 무사히 통과할 수 있었다.

'''
Q. find pivot index 724
정수배열인 nums가 주어졌을 때 해당 배열의 pivot의 index를 구하는 것이 목표.
pivot을 정하는 기준은 left,right로 나누어서 양 쪽의 합이 같아지는 지점
단,pivot을 제외하고 계산함.

left sum = 0 일 경우도 계산해야함 -> 까다로울수도


'''


def pivotIndex(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    total_sum = sum(nums)
    left_sum = 0

    pivot = 0

    for i in range(0,len(nums)):
        pivot = i
        total_sum -= nums[i]
        #pivot을 빼줌

        if total_sum == left_sum :
            return pivot

        left_sum += nums[i]



if __name__ == '__main__':
    nums = [1, 7, 3, 6, 5, 6]
    nums2 = [2,1,-1]

    print(pivotIndex(nums2))