[leetcode - Java] 209. Minimum Size Subarray Sum

1. 문제

---

- 배열의 연속된 요소를 더해 target이 되는 최소 길이를 구하여라.

2. 의사 코드

---

"배열의 요소를 적게 사용하여 요소들의 합이 target과 동일하게 만들 것." 가장 먼저 생각해본 부분으로 이에 맞는 코드를 구현해보려 했다.

1. 배열 정렬(큰 요소부터 더해 target과 가까워지기 위해) 및 필요한 지역변수 선언
    Arrays.sort(nums);
    int left = 0;
    int right = nums.length-1;
    int sum = 0;
    int result = nums.length-1;

2. 가장 적게 배열 요소를 조합하여 target과 일치해야 하기에 정렬된 배열의 뒷 요소부터 인덱스 활용
    int right = nums.length-1;
3. 반복문 실행
    sum += nums[right];
    right --;
4. 조건문으로 sum이 target을 넘었을 때 등등 설정

3. 시도

---

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        Arrays.sort(nums);
        int numsSum = Arrays.stream(nums).sum();
        System.out.println("nums = " + Arrays.toString(nums));

        int left = 0;
        int right = nums.length-1;
        int sum = 0;
        int result = nums.length-1;


        if (numsSum < target) {
            return 0;
        }
        for (int n : nums) {
            if (n == target) {
                System.out.println("n = " + n);
                return 1;
            }
        }
        while (true) {
            sum += nums[right];
            System.out.println("1 sum = " + sum);
            if (sum == target) {
                return result - right+1;
            }
            while (sum >= target) {
                sum -= nums[right];
                System.out.println("2 sum = " + sum);
                left++;
                System.out.println("1 left = " + left);
            }
            System.out.println("1 right = " + right);
            right--;
            System.out.println("2 right = " + right);
            if (right <= 0) {
                return result - right;
            }
        }
    }
}

실패한 테스트 케이스도 많고 다른 조건에 대한 처리도 필요했다. 배열 전체의 합이 target보다 작다거나, 요소 한 개가 target과 같다거나 등등.

4. 개선

---

처음에 투 포인터를 활용해 문제를 해결하려 했지만, 이 문제와 같이 연속된 요소를 다룰 때에는 슬라이드 윈도우 방식을 많이 사용한다는 것을 보게되었다. 그리고 최소 길이와 같은 것들을 구해야할 때 초기 값으로 가장 큰 값을 설정해 Math.min() 함수로 비교한다고 한다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        System.out.println("1 minLength = " + minLength);

        while (right < nums.length) {
            sum += nums[right];
            System.out.println("1 sum = " + sum);
            System.out.println("right = " + right);

            while (sum >= target) {
                minLength = Math.min(minLength, right-left+1);
                System.out.println("2 minLength = " + minLength);
                sum -= nums[left];
                System.out.println("2 sum = " + sum);
                System.out.println("1 left = " + left);
                left++;
                System.out.println("2 left = " + left);
            }
            right++;

        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

먼저 큰 수 minLength를 만들었다. 요소들의 합이 target보다 높을 때는 min 함수를 활용하여 sum을 구할 때 사용한 요소들의 가장 뒷 인덱스 번호right - left(앞 인덱스번호) +1(요소들의 개수를 구해야 하기에) 하여 최솟값을 구해주었다.

슬라이드 윈도우 흐름은 아래와 같다.