LeetCode 209번: Minimum Size Subarray Sum(JAVA)
문제출처 209번: Minimum Size Subarray Sum
❔ 문제
양의 정수 배열 nums의 부분 배열 중 합이 target 이상이 되는 최소 부분 배열의 크기를 구하는 문제.
⏩ 예시
Input: ntarget = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
❕ 문제풀이
public static int minSubArrayLen(int target, int[] nums) {
int s = 0;
int e = 0;
int result = nums.length + 1;
if (nums.length == 1) return target <= nums[0] ? 1 : 0; // 1.
int sum = nums[s];
while (s <= e && e < nums.length) { // 2.
if (sum >= target) result = Math.min(e-s+1, result); // 3.
if (sum > target) { // 4.
sum -= nums[s++];
} else if (sum <= target && e + 1 < nums.length) {
sum += nums[++e];
} else {
break;
}
}
return result == nums.length+1 ? 0 : result; // 5.
}
- 배열의 크기가 1이면서 원소가 target보다 크거나 같다면 만족하는 최소 크기 1을 반환
- 투포인터에 사용될 index s와 e가 while문에서 탈출할 조건
- loop를 순환하면서 부분 배열의 합 sum이 target보다 크거나 같을 경우, 결과값 result와 비교하여 작은 부분 배열의 크기를 대체
- 부분 배열의 합이 클 경우 s를 작거나 같을 경우는 e를 한칸 증가시켜 부분 배열의 합을 변화시킨다.
- 결과값이 한번도 대체되지 않았다면 답이 없으므로 0, 아닐 경우 결과값을 반환한다.
💯 고찰
문제해결 과정을 머릿속에 구상한 부분까지 구현하여 채점을 했지만, 결과 값의 제약을 같을 때의 조건으로만 생각하여 많이 돌아갔다. 또한 크거나 같다는 조건으로 수행할 시 전체를 순환해야 하기에 탈출 조건을 다시 설계해야했다.
따라서 코드가 생각보다 어지러워지긴 했지만 최대한 결과에 맞게 구성하였다.
public int minSubArrayLen(int target, int[] nums) {
int ans =Integer.MAX_VALUE;
int sum=0;
int i=0;int j=0;
while(j<nums.length){
sum+=nums[j];
while(sum>=target){
ans=Math.min(ans,j-i+1);
sum-=nums[i++];
}
j++;
}
if(ans==Integer.MAX_VALUE){
return 0;
}
else {
return ans;
}
}
참고한 위 솔루션은 sliding window 방식을 이용한 풀이였다.
투포인터 방식과 상당히 유사하지만 비교 조건을 훨씬 간단하게 수행할 수 있기 때문에 코드가 훨씬 더 간결하다.
