[알고리즘] LeetCode - Minimum Size Subarray Sum

Minimum Size Subarray Sum - LeetCode

문제 설명

• 정수형 배열 nums가 양의 정수로 채워져서 주어진다.
• nums에서 합이 target이 되는 하위 배열(연속된 수)을 찾고, 그 길이를 반환해야 한다. 단, 그 중 가장 짧은 길이를 반환해야 한다.
• 합이 target이 되는 연속된 하위 배열이 없는 경우 0을 반환한다.

문제 해결

• 반복문을 돌면서 정수형 변수 sum이 target보다 커지는 지점을 찾고, 그 지점에서 앞부분의 수를 하나씩 빼면서 target보다 크거나 같고 가장 짧은 길이를 찾는다.
• 중간에 조건을 만족할 때마다 해당 지점의 하위 배열의 길이의 최솟값을 갱신한다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int N = nums.length;
        
        int head = 0, tail = 0;
        int sum = 0;
        int answer = Integer.MAX_VALUE;

        while(tail < N) {
            sum += nums[tail];

            if (sum >= target) {
                do {
                    int now = tail - head + 1;
                    answer = Math.min(answer, now);
                    sum -= nums[head];
                    head++;
                } while(sum >= target);
            }

            tail++;
        }

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

결과

시간	메모리
1 ms	55.8 MB

 

---

성능 개선

1차 시도

1. 풀이 코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int N = nums.length;

        for (int w = 1; w <= N; w++) {
            for (int i = 0; i <= N - w; i++) {
                int sum = 0;
                for (int j = i; j < i + w; j++) {
                    sum += nums[j];
                }
                if (sum >= target) {
                    return w;
                }
            }
        }
        return 0;
    }
}

2. 문제점

• 매 윈도우마다 합을 계산하는 반복문으로 인해 전체 시간 복잡도가 O(n^3)이다.
• 배열의 최대 크기가 100,000(십만) 이라 연산량이 100,000,000(일억) 번을 훌쩍 넘어버린다.
• 시간 초과로 인해 실패 한다.

3. 결과

---

2차 시도

1. 풀이 코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int N = nums.length;

        for (int w = 1; w <= N; w++) {
            int sum = 0;
            for (int i = 0; i <= N - w; i++) {
                if (i == 0) {
                    for (int j = 0; j < w; j++) {
                        sum += nums[j];
                    }
                } else {
                    sum = sum - nums[i - 1] + nums[i + w - 1];
                }
                if (sum >= target) {
                    return w;
                }
            }
        }
        return 0;
    }

2. 1차 시도 코드 개선점

• 매 윈도우마다 반복하는 반복문을 제거하고 i가 0인 경우에 한번만 계산하도록 개선했다.
• 윈도우가 바뀔 때 한번만 합을 계산하고 이후로는 앞의 값을 빼고, 뒤의 값을 더하는 방식으로 개선했다.

3. 문제점

• 매 윈도우마다 합을 계산하는 반복문은 제거했지만 그래도 시간 복잡도가 O(n^2)이다.
• 배열의 최대 크기가 100,000(십만) 이라 연산량이 10,000,000,000(백억) 번이라 1초안에 해결할 수 없다.

4. 결과

---

3차 시도

1. 풀이 코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int N = nums.length;
        
        int head = 0, tail = 0;
        int sum = 0;
        int answer = Integer.MAX_VALUE;

        while(tail < N) {
            sum += nums[tail];

            if (sum >= target) {
                do {
                    int now = tail - head + 1;
                    answer = Math.min(answer, now);
                    sum -= nums[head];
                    head++;
                } while(sum >= target);
            }

            tail++;
        }

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

2. 2차 시도 코드 개선점

• 반복문으로 target값 조건을 만족하는 지점까지 돌고, 이후 앞에서 부터 값을 하나씩 빼면서 targe값 조건을 만족하고 가장 짧은 길이의 하위 배열을 찾았다.

3. 결과