[LeetCode] 209 Minimum Size Subarray Sum JavaScript

문제 링크

Minimum Size Subarray Sum - LeetCode

 

문제 유형

배열 (Array), 투 포인터 (Two Pointer)

 

문제 풀이

해당 문제는 배열 내의 어떤 부분 배열의 원소의 전체 합이 target값과 같거나 큰 부분 배열의 최소 길이를 출력해야 한다. 이는 투 포인터의 개념을 이용하여 해결하면 된다.

투 포인터는 1차원 배열을 순차적으로 접근할 때, 2개의 포인터를 사용하여 문제를 처리한다. 따라서, 어떤 배열 원소들의 특정 합이 되는 부분 배열을 구할 때 유용하다.

 

1. 조건을 만족하는 부분 배열의 최소 길이를 저장하는 n, 시작점 start, 투 포인터 사이의 값들의 합을 저장하는 sum을 초기화한다.
   이때, 시작점과 끝점은 처음에 배열의 첫번째 원소의 인덱스를 가리킨다.
2. 배열을 순차적으로 접근하면서 끝점이 가리키는 값을 더하면서 현재 부분합을 저장한다.
3. 부분 합이 target과 같거나 크면 시작점을 한칸씩 움직이면서 시작점이 가리키는 값을 빼면서 현재 부분합을 저장한다.
   부분 합이 target과 같거나 크면 문제가 원하는 최소 길이의 후보가 되므로 최소 길이를 비교하여 훨씬 더 작은 길이를 저장한다.
4. 2,3을 배열 마지막까지 반복했음에도 n이 처음에 저장한 무한대 값이면 0을 출력하고, 아니면 부분 배열의 최소 길이 n를 출력한다.

+) Infinity 는 전역 객체의 속성이자 전역 스코프의 변수로, 양의 무한대를 나타내는 숫자이다.

Number.MAX_SAFE_INTEGER는 JavaScript에서 안전한 최대 정수값(2^53 - 1)을 나타내는 상수이다.

처음에는 Number.MAX_SAFE_INTEGER 를 사용하여 n을 매우 큰 값으로 설정했는데, Infinity 를 사용했을 때 3~40%나 빠르게 실행되었다.

 

코드

var minSubArrayLen = function(target, nums) {
    let n = Infinity; // Infinity: JS에서 미리 정의된 양의 무한대를 나타내는 정수
    let start = 0;
    let sum = 0;
    for (let end = 0; end < nums.length; end++) {
        sum += nums[end];
        while (sum >= target) {
            n = Math.min(n, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }
    
    return n === Infinity ? 0 : n;
};

 

참고

https://www.youtube.com/watch?v=6gQm5De94aU&list=PLDV-cCQnUlIYFOXYzqLoXnEye4WxDa_30&index=5