소프트웨어에 대한 모든 것

LeetCode 풀기 - 1413. Minimum Value to Get Positive Step by Step Sum 본문

알고리즘/LeetCode

LeetCode 풀기 - 1413. Minimum Value to Get Positive Step by Step Sum

앤테바 2021. 11. 12. 08:34
반응형

1413. Minimum Value to Get Positive Step by Step Sum

문제)

솔루션1)

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        if nums[0] > 0:
            start = 1
        else:
            start = abs(nums[0]) + 1
        
        while True:
            r = start            
            for n in nums:
                if r+n <= 0:
                    break
                r += n
                
            else:
                return start
            start += 1

솔루션2)

계속 누적해서 더한 경우의 가장 작은 값이 나올텐데, 이 값을 1 이상으로 만들어주는 값을 찾으면 된다.

아래 테이블과 값이 초기 값을 0 으로 주고 계속 더해 나갔을 때 가장 최소값은 -4이다. 

그렇다면 5 이상의 값을 초기값을 설정해서 계산하게되면 최소값을 1이 되기 때문에 값이 5가 되는 것이다.

idx nums[i] sum 최소값
0 -3 0 (초기값) - 3   = -3 -3
1 2 -3 + 2 = -1 -4
2 -3 -1 - 3  = -4 -4
3 4 -4 + 4 = 0 -4
4 2 0 + 2  = 2 -4

 

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        return abs(min(accumulate(nums, initial=0))) + 1

 

반응형
Comments