1413. Minimum Value to Get Positive Step by Step Sum

https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/description/

문제

정답

1. 처음 풀이 (공간 복잡도 O(N))

class Solution {
    public int minStartValue(int[] nums) {
        // prefix sum을 구하고, 거기서 가장 작은값을 구하자. 
        // 그럼 걔를 더해줬을 때 (거기까지 진행했을 때) 1이상 이어야 하니까,
        // (가장 작은값일 때 만족하는 숫자라면, 나머지는 더 큰 값이므로, 더해줘도 무조건 1이상임)
        // answer + min >= 1 
        // answer >= 1 - min
        // asnwer의 최소값은 1 - min이 된다.
        int answer = 0;
        int[] prefix = new int[nums.length];
        prefix[0] = nums[0];
        int min = prefix[0];
        for(int i = 1; i < nums.length; i++ ) {
            prefix[i] = prefix[i-1] + nums[i];
            min = Math.min(min, prefix[i]);
        }

        // min값이 양수라면 무조건 1이 정답
        if(min > 0) {
        	answer = 1;
            return answer;;
        }
		
        answer = 1 -min;
        return answer;
    }
}

• 반복문을 한 번만 순회하므로 O(N)의 시간복잡도를 가짐
• [-3,2,-3,4,2] 배열의 각 인덱스를 더해가면서 연산(합)의 결과가 항상 1을 만족하는 최소값을 구해야함
• 그렇다면 해당 배열의 인덱스를 더해가면서 존재하는 가장 낮은 최악의 합을 만족하면 모든 조건을 만족한다.
  • 목표 인덱스에 도착할 때마다 거기까지의 합을 새로 구한다면 O(N^2)의 시간복잡도를 가진다.
  • 누적합에서 O(N)으로 해결할 수 있는 방법은? -> prefix sum
  • prefix sum을 구하고, prefix sum의 최악(최소)값을 구하면 O(N)으로 해결 가능!
• answer + prefix sum의 최악값(min) >= 1을 만족해야하므로, answer >= 1 - min
  • answer의 최소값은 1 - min!
  • 단, prefix sum의 모든 값이 양수라면 (min값이 양수라면) 정답은 무조건 1이다.

=> prefix sum 배열을 어차피 한번만 사용하므로, 굳이 배열을 만들지 않고 반복문 내에서 해결할 수 있다.

2. 다른 풀이 (공간 복잡도 O(1))

class Solution {
    public int minStartValue(int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 0; i < nums.length; i++ ) {
            sum += nums[i]; // 공간 복잡도 O(1)으로 누적합 구하기
            min = Math.min(min, sum);
        }

        // min값이 양수라면 무조건 1이 정답 (1로 안내려가니까)
        if(min > 0) {
            return 1;
        }

        return  1 - min ;
    }
}

• prefix sum을 재사용하지 않고, for 루프를 돌면서 각 값을 한번씩만 사용하므로 별도의 배열에 저장하지 않음
  -> 공간 복잡도를 O(1)으로 최적화