[java] Minimum Size Subarray Sum

[참고문제] : https://leetcode.com/problems/minimum-size-subarray-sum/

Minimum Size Subarray Sum - LeetCode

문제 풀이

연속된 subArray를 어떻게 관리할지가 포인트인 문제다.

 

생각의 흐름 - 한번만 배열을 읽자

물론 문제를 풀면서 달라질 수 있지만, 일단 주어진 nums배열은 한번만 읽는게 중요할 것으로 보였다.

 

생각의 흐름 - SubArray를 어떻게 관리하지?

처음에는 단지 배열에 저장하자고 생각했는데, sum을 계산한 배열이 필요할 거라 생각했다. 그래야 배열을 다시 읽어 합치는 과정을 안해도 된다.

그러나 최소 길이를 찾아야 하니, 시작과 끝 지점을 알아야 하는데, 처음에는 queue에 저장하고 길이를 알아볼까 했지만, 그러면 계산된 sum 처리가 어려워서 left, right 인덱스를 관리하자고 생각했다.

 

생각의 흐름 - 언제 left와 right를 늘리거나 줄여주는가?

right는 자연스럽게 배열을 읽어나가면서 늘리면 된다. 내가 필요한건 결과값인 minLength이고, left와 right 둘다 길이 계산에서 필요한 값이기 때문에 minLength계산만 되면 어떻게 되든 상관없다.

 

right가 문제가 아니라 left가 문제다.

결국 sumArr에 대해, 현재까지 더해진 값에 left를 늘려주며 그 값을 빼면, 앞에서부터 left 까지 누적된 sumArr를 뺄 수 있다.

그 값을 통해, sum 값이 target보다 크거나 같게되는 지점을 찾는다.

 

public int minSubArrayLen(int target, int[] nums) {
    int result = 0;
    int left = 0;
    int right = 0;
    int[] sumArr = new int[nums.length];
    Arrays.fill(sumArr, 0);
    int minLength = Integer.MAX_VALUE;

    for(int i = 0; i < nums.length; i++) {
        if(nums[i] >= target) {
            return 1;
        }

        if(i == 0) {
            sumArr[i] = nums[i];
        } else {
            sumArr[i] = sumArr[i-1] + nums[i];
        }
        right ++;

        if(sumArr[i] >= target) {
            while(left < right) {
                if((sumArr[i] - sumArr[left]) >= target) {
                    left ++;
                } else {
                    break;
                }
            }

            minLength = Math.min(minLength, right - left);
        }
    }

    if(minLength != Integer.MAX_VALUE)
        result = minLength;

    return result;
}