티스토리 뷰
[LeetCode - Daily Challenge] 1413. Minimum Value to Get Positive Step by Step Sum
Jaime.Lee 2021. 11. 12. 10:30Problem
Given an array of integers nums, you start with an initial positive value startValue.
In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).
Return the minimum positive value of startValue such that the step by step sum is never less than 1.
Example 1:
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
Example 2:
Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.
Example 3:
Input: nums = [1,-2,-3]
Output: 5
Constraints:
- 1 <= nums.length <= 100
- -100 <= nums[i] <= 100
Solution
초기 값을 설정하고 주어진 배열을 순차적으로 탐색하면서 더하는 동안 합이 0이하로 떨어지지 않게 하는 최소한의 양수 값을 구하는 문제입니다.
초기 값은 양수 중 가장 작은 수인 1부터 설정 가능합니다.
배열을 탐색하면서 더하는 동안 음수가 포함되어 있을 경우 합이 음수가 될 수도있지만 사전에 양수를 먼저 더했을 경우엔 그렇지 않을 수도 있음을 주의하고 풀어야 합니다.
풀이 방법은 순차적으로 더하는 동안 가장 낮은 값이 되었을 때를 따로 저장했다가 절대값을 취한 뒤 1을 더해주면 됩니다.
그렇게 하기 위해선 현재 합계와 가장 낮은 합계를 따로 관리해야 합니다.
가장 낮은 합계는 한 번도 0이하로 내려가지 않을 수 있기 때문에(모두 양수인 경우) 초기값을 0으로 설정해야 마지막에 1이 더해져도 정답 조건을 만족시킬 수 있습니다.
public class Solution {
public int minStartValue(int[] nums) {
int lowestSum = 0;
int sum = 0;
for (int num : nums) {
sum += num;
lowestSum = Math.min(sum, lowestSum);
}
return Math.abs(lowestSum) + 1;
}
}
Test
package io.lcalmsky.leetcode.minimum_value_to_get_positive_step_by_step_sum;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
class SolutionTest {
@Test
void testAll() {
assertAll(
() -> test(new int[]{-3, 2, -3, 4, 2}, 5),
() -> test(new int[]{1, 2}, 1),
() -> test(new int[]{1, -2, -3}, 5)
);
}
private void test(int[] given, int expected) {
// when
Solution solution = new Solution();
int actual = solution.minStartValue(given);
// then
assertEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode - Daily Challenge] 739. Daily Temperatures (0) | 2021.11.14 |
---|---|
[LeetCode - Daily Challenge] 203. Remove Linked List Elements (0) | 2021.11.13 |
[LeetCode - Daily Challenge] 122. Best Time to Buy and Sell Stock II (0) | 2021.11.11 |
[LeetCode - Daily Challenge] 404. Sum of Left Leaves (0) | 2021.11.05 |
[LeetCode - Daily Challenge] 129. Sum Root to Leaf Numbers (0) | 2021.11.03 |
- Total
- Today
- Yesterday
- 함께 자라기
- 스프링부트
- 스프링 부트 튜토리얼
- Linux
- 스프링 부트 회원 가입
- @ManyToOne
- Spring Boot JPA
- intellij
- 스프링 데이터 jpa
- 스프링 부트
- 헥사고날 아키텍처
- Spring Data JPA
- 클린 아키텍처
- leetcode
- QueryDSL
- Spring Boot Tutorial
- 알고리즘
- 함께 자라기 후기
- Jackson
- JSON
- proto3
- spring boot app
- 스프링 부트 애플리케이션
- Spring Boot
- gRPC
- spring boot application
- r
- JPA
- Java
- spring boot jwt
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |