[Leetcode] 209. Minimum Size Subarray Sum - JS

https://leetcode.com/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
양의 정수 배열 nums와 양의 정수 target이 주어진다.
target보다 크거나 같은 부분 배열 합의 최소 길이를 구하여라.
만약 존재하지 않는다면 0을 반환하라.

제한조건
--------------------
- 1 <= target <= 10^5
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4

 

2. 접근 방법

접근방법 - Sliding Window
--------------------
1. start, end를 각각 0, subArraySum을 nums 첫번째 요소로 초기화한다.
2. start <= end && end < nums.length 를 만족하면 반복한다.
    - end가 마지막 인덱스에 도달하면 모두 순회한 것이므로...
    - start가 end를 넘어가는 경우에도 반복을 종료한다. 불필요한 연산이 되지 않도록...
3. 만약 부분 배열의 합 >= target 만족하면, 
    - minValue와 start와 end 사이의 길이 중 작은 값을 할당
    - 다음 subArraySum 비교를 위해 nums[start]를 빼준다.
    - start를 우측으로 이동한다. 
    - start 이동 시키는 이유는 이전 위치에서 최소 부분 배열 길이는 구했으므로 다음 인덱스에서 최소 부분 배열이 있는지 확인하기 위함이다.
4. 만약 부분 배열의 합 < target 이면,
    - end 우측 이동
    - 부분 배열의 길이를 증가
5. 반복문이 종료되었을 때, minValue가 Infinity 그대로면 부분 배열의 합이 target 보다 크거나 같은 경우가 없는 것이므로 0을 반환

부분 배열의 합과 target을 비교하여 window의 사이즈(크기)를 구한다.

window 사이즈 구한 뒤에는 시작 인덱스를 이동시키면서 window를 움직일 수 있다.

window를 움직임에 따라 이전 window에서 계산했던 로직을 다시 계산하지 않아도 된다.

 

3. 코드

var minSubArrayLen = function(target, nums) {
    let start = 0;
    let end = 0;
    let minValue = Infinity;
    let subArraySum = nums[start];

    while (start <= end && end < nums.length) {
        if (subArraySum >= target) {
            minValue = Math.min(minValue, end - start + 1);
            subArraySum -= nums[start];
            start++;
        } else {
            end++;
            subArraySum += nums[end]
        }
    }
    return minValue === Infinity ? 0 : minValue;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

나도 sliding window 방법으로 풀기 위해 window 크기를 nums 배열 길이부터 시작하여 줄여 나가는 방법으로 접근했다.

하지만 부분 배열의 길이를 줄여나가는 반복분 안에서 무조건 부분 배열의 시작을 nums의 첫번째 인덱스부터 시작하면서 해당 길이만큼의 부분 배열의 시작 위치를 이동시키는 반복문을 중첩 반복문으로 설계 하니 시간 초과가 발생했다.

 

다른 사람의 풀이를 참고하여, 첫번째 인덱스를 기준으로 부분 배열의 합과 target을 비교하여 window 크기를 구한 뒤 이후에는 시작 인덱스를 이동하면서 이미 계산했던 내용을 다시 계산하지 않도록 구현했다.

 

sliding window 패턴을 유데미 알고리즘 강의에서 배운 적이 있었는데, 관련 문제를 많이 접해보지 못해서 어려웠다. 반복 학습하면서 익숙해져야겠다.

 

 

5. 좀 더 쉬운 sliding window 풀이 (feat. GPT)

두번째 풀 때에도 머릿속에 잘 안떠올라서 GPT에게 물어봐서 sliding window 개념을 좀 더 쉽게 접근해서 풀어보았다.

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let minLen = Infinity;
    let start = 0;
    let sum = 0;

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        
        while (target <= sum) {
            sum -= nums[start];
            minLen = Math.min(i - start + 1, minLen);
            start++;
        }
    }
    return minLen === Infinity ? 0 : minLen;
};

 

기존 풀이보다 변수도 줄어들고 조건문도 1개로 줄어들어 훨씬 이해하기 쉬운 코드가 되었다.

접근 방법은 최소길이(minLen)을 가장 큰 수로 초기화 하는 것과 sliding window의 시작 포인터(start)를 0으로 초기화 하는 것 까진 동일하다.

 

sliding window의 마지막 포인터는 for문의 i와 동일하게 이동할 수 있다.

for 문 안에서 sum에 nums 요소를 추가할 때 마다 target <= sum 조건을 체크한다.

조건을 만족하면 sum에서 nums의 start 위치의 요소를 빼주면서 반복적으로 조건을 체크한다.

그 때마다 최소길이(minLen)와 시작 포인터(start)를 갱신해준다.