내일은 알고리즘

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

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

슬라이딩 윈도우와 비슷한 느낌으로 구현했는데, 좌측합이 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))

https://leetcode.com/problems/running-sum-of-1d-array/

LeetCode의 14일짜리 코스를 시험삼아 시작해봤습니다.

하루에 2문제씩 14일간 28문제를 푸는 코스네요.

배열의 누적합 문제입니다.

딱히 설명할 부분은 없는 간단한 문제였습니다.

LeetCode에서 주어지는 Example 코드가 Python 3.5 이상에서만 돌아가는 코드여서 주석처리 했습니다.

class Solution:
    # def runningSum(self, nums: List[int]) -> List[int]:
    def runningSum(self, nums: list) -> list:
        sum = 0
        answer = []
        for i in nums:
            sum += i
            answer.append(sum)
        
        return answer


input = [[1,2,3,4],[1,1,1,1,1],[3,1,2,10,1]]
for i in input:
    print(Solution().runningSum(i))