Time Limit Exceeded 1

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    // subarray 길이 지정
    for(let i = 0; i < nums.length; i++){
        // subarray 시작 인덱스 지정
        for(let j = 0; j < nums.length - i; j++){
            // slice로 subarray 생성
            const subArray = nums.slice(j, j + i + 1);

            const sum = subArray.reduce((acc, curr) => {
                return acc + curr;
            }, 0);

            if(sum >= target){
                return subArray.length;
            }
        }
    }

    return 0;
};

이중 for문에 매 반복마다 slice()와 reduce()까지 있어서 시간 복잡도가 상당하다.
그로 인해서 시간 초과가 되었다.
반복문을 최대한 줄여봐야겠다.

Time Limit Exceeded 2

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    // subarray 길이 지정
    for(let i = 0; i < nums.length; i++){
        // subarray 시작 인덱스 지정
        for(let j = 0; j < nums.length - i; j++){
            // j부터 j+i까지의 합 === subarray 원소의 합
            let sum = 0;
            
            for(let k = j; k < j + i + 1; k++){
                sum += nums[k];
            }

            if(sum >= target){
                return i + 1;
            }
        }
    }

    return 0;
};

이번에는 slice()를 제거해보았다.
그러나 여전히 3중 for문이었고, reduce의 역할이 for문으로 변경되는 바람에
시간 복잡도 측면에서는 큰 변화가 없었고, 시간 초과가 발생했다.

Time Limit Exceeded 3

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    // 일반적인 sliding window는 길이가 주어지는데
    // 이 문제는 길이를 구하는게 목적이기 때문에, 유동적인 길이를 내가 제어할 필요가 있음.

    // subarray의 길이 설정. 1 ~ nums.length의 길이를 가질 수 있다.
    for(let i = 1; i <= nums.length; i++){
        // tempSum 구하기
        let tempSum = 0;

        for(let j = 0; j < i; j++){
            tempSum += nums[j];
        }

        // subarray의 합 구하기
        for(let j = 0; j <= nums.length - i; j++){
            if(tempSum >= target){
                return i;
            }

            // 다음 subarray로 이동
            // subarray의 가장 앞에 있던 것을 빼주고,
            // subarray의 가장 끝의 다음에 있던 것을 더해준다.
            // 즉, 옆으로 한칸 밀었다고 생각하면 된다.
            tempSum = tempSum - nums[j] + nums[j+i]
        }
    }

    return 0;
};

이번에는 3중 for문을 제거하고 2중 for문까지 줄여보았다.
또한, sliding window 알고리즘을 적용해보고자 했다.
덕분에 for문의 깊이는 줄어들었지만 여전히, 반복 횟수가 많아서 시간 초과 문제가 발생했다.

solution

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    // subarray는 0번 인덱스를 기준으로 subarray의 길이를 늘려 기존 배열의 끝까지 닿았다가,
    // 답이 구해지지 않으면
    // 1번 인덱스를 기준으로 subarray의 길이를 늘려 기존 배열의 끝까지 닿았다가, ...
    // 위와 같은 방법을 반복하면서 정답을 찾아간다.
    // 문제에서 원하는 답은 minimal length이기 때문에 이 방법을 사용하더라도
    // 다른 기준들에 대해서 다 비교를 해줘야한다.
    // 따라서 minLength를 두고, 최소값이 나오면 계속 교체하는 방법을 사용한다.

    let start = 0; // subarray 시작점
    let end = 0; // subarray 끝점
    let length = 1; // subarray 길이
    let minLength = Infinity; // 최소 subarray 길이. Infinity로 설정해야 어떤 초기값이 와도 최소 값으로 설정할 수 있다.
    let sum = 0; // subarray 원소 합

    while(start < nums.length){
        // subarray의 누적 합
        sum += nums[end];
        
        // 정답을 만족하는 경우 최소 길이 갱신 후 다음 연산 진행
        if(sum >= target){
            minLength = Math.min(minLength, length);
    
            // 여기서 if를 통해서 end가 끝인지 아닌지 판별해줘야함
            if(end === nums.length - 1){
                sum = 0;
                start++;
                end = start;
                length = 1;
            } else {
                end++;
                length++;
            }

            continue;
        }

        // end가 기존 배열의 끝에 닿았다면
        // 현재 start 인덱스를 기준으로 한 subarray는 연산이 종료되었으므로
        // sum을 초기화하고, 다음 기준점으로 넘어가기 위해 start를 증가시킨다.
        if(end === nums.length - 1){
            sum = 0;
            start++;
            continue;
        }

        // 정답이 아닌 경우 subarray의 길이를 늘린다.
        // 또한, 누적 합을 위해 end도 늘린다.
        end++;
        length++;
    }

    return minLength === Infinity ? 0 : minLength;
};

이번에는 이전 시도에서 완전히 적용하지 못했던 sliding window 알고리즘을 적용해냈다.
덕분에 반복문은 중첩이 되지 않았다.
4개의 값(start, end, length, sum)을 기준으로 연산을 해나간다.

start 지점을 기준으로 subarray의 길이가 1인 것부터 시작해서,
만들 수 있는 최대 길이까지 늘려간다.
그 과정에 조건에 충족하는 값이 나오면 minLength와 비교하여 최소값을 저장한다.
이 후, subarray의 크기가 최대로 커졌다면 값들을 초기화하고 시작점을 이동하며,
그게 아니라면 subarray의 크기를 키우고 연산을 반복한다.

조건에 충족하는 값이 나오지 않더라도 다음 연산을 진행해야하므로,
동일한 로직을 사용해서 다음 연산으로 넘어간다.

다른 분의 solution

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let start = 0;
    let end = 0;
    let sum = 0;
    let minLength = 0;
    
    while(end < nums.length) {
        // subarray 원소를 누적합
        sum += nums[end];
        
        // 조건에 부합한다면
        // 연산을 진행하며 끝점(end)이 가장 작을 때이기 때문에
        // 이 순간 이후로 현재 subarray 시작점을 유지할 필요가 없음.
        while(sum >= target) {
            // subarray의 길이
            let length = end - start +1;

            // 최소 길이가 0이거나, subarray의 길이가 현재까지의 최소 길이보다 작다면
            // 현재 subarray의 길이를 최소 길이에 할당한다.
            // 왜 최소 길이가 0일 때를 조건으로 해도 되느냐?
            // 이 while문에 들어오기 위해서는 subarray의 합이 target보다 같거나 커야하는데
            // 계속해서 조건을 만족하지 못한다면 0인 채로 남아 있기 때문.
            // 이 while문을 한번도 들어오지 못한채로 종료되면 그 것은 그것대로 0을 반환할 수 있다.
            if(minLength === 0 || length < minLength) minLength = length;
            
            // 왜 갑자기 subarray의 합에서 맨 앞을 빼느냐?
            // subarray를 한칸 옮기기 위해서 맨 앞의 값을 빼고, 맨 뒤의 다음 값을 더해줘야하기 때문.
            sum -= nums[start];

            // subarray의 시작점을 한칸 옮긴다.
            start++
        }

        // 조건을 만족하지 못한다면 subarray의 길이를 늘린다.
        // 이 때, 시작점(start)는 그대로라는 점!
        end++;
    }

    return minLength;
};

이 분도 필자와 동일하게 sliding window 알고리즘으로 문제를 해결하셨다.
그런데 왜 필자보다 성능이 훨씬 좋은걸까? 심지어 필자는 반복문도 한번만 사용했는데 말이다.

이 분과 필자의 풀이는 언제 연산을 끊었는가에 차이가 있다.
필자는 반복문을 사용하지는 않았지만, 결국 모든 케이스에 대해서 subarray의 길이를 계산했다.
그러나 이 분은 반복문은 한번 더 사용했지만, 현재 subarray에서 나올 수 있는 최소의 길이가 확정되면,
바로 그 subarray에 대한 연산을 중단하셨다.

같은 알고리즘을 사용하더라도 불필요한 작업을 끊어내는 것으로 더 큰 차이를 만들어 낼 수 있다는 것을 느꼈다.