🟠[Leet code -209] Minimum Size Subarray Sum ✅

Minimum Size Subarray Sum - LeetCode

문제

• Input
  양의정수 배열 nums, 양의 정수 target
• Output
  합이 target 이상인 부분 배열중 길이가 가장 짧은 것의 길이 반환, 없다면 0 반환

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관없음 | O(log n) : 크게  상관없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$1 \le n \le 100'000$으로, $n \log n$ 부터 고려가능하다.

 

 

해결 과정

연속된 부분 배열을 다루어야하기 때문에 자연스럽게 투 포인터를 생각했다.

투 포인터 안에 있는 배열의 합을 sum이라고 한다면, 대강 생각해 보았을 때 target과 sum의 관계를 이용하여 둘 중 어떤 게 크다면 왼쪽을 움직이고, 반대면 오른쪽을 움직인다던지, 이런 느낌처럼 해보면 괜찮겠다고 생각하여 더 자세히 생각해 봤다.

 

그래서 우선 투 포인터가 모두 0부터 시작한다고 가정할 때, 처리해야 하는 두 가지의 경우를 생각했다. 

• target <= sum
  정답의 후보가 된다. 하지만 이 이상 오른쪽 포인터를 늘려봤자, 현재의 정답 후보보다 길이가 길기 때문에 의미가 없다.
  따라서 현재 길이를 정답 후보로 갱신하고, 더 짧은 구간을 찾기 위해 왼쪽 포인터를 증가시킨다.
• sum < target
  sum을 키워야 한다 => 부분배열을 늘려야 한다
  왼쪽 포인터를 감소하여 부분배열을 늘리는 것은 이미 탐색했던 구간이 다시 포함되기 때문에,
  오른쪽 포인터를 증가하여 부분배열의 크기를 늘린다.

그리고 아래와 같은 수도 코드를 작성했다.

WHILE (r < nums.size)
{      
    IF (총합이 target 이상일 때)
        ret업데이트
        ++l
        sum 업데이트
        
    IF (총합이 target 미만일 때)
        ++r
        sum 업데이트
}

해당 방법은 최대 2n이므로 $O(n)$의 복잡도를 가지기 때문에 충분히 통과 가능한 복잡도이며,

마지막으로 $1 \le nums[i] \le 10'000$으로, 최대 합이 1'000'000'000이 되어 int로 충분함을 확인했다.

 

 

구현

추가적으로 작성한 것들 중에 input으로 들어오는 nums에 -1을 추가하였는데, 이는 Out of range를 막기 위한 조건문을 고민하다가 그냥 쓰레기 값 하나를 추가하면 편하지 않을까?라는 생각에 시도했는데 잘 동작되었다.

하지만 생각해 보면 엄청 효율적이지는 않은 것 같다..ㅎ

 

그리고 std::min연산의 예외를 처리하기 위해 ret을 INT_MAX로 정의했다.

int minSubArrayLen(int target, vector<int>& nums) 
{
    int n = nums.size();
    nums.push_back(-1);

    int l = 0; int r = 0;
    int ret = INT_MAX;

    int sum = nums[0];
    while (r < n)
    {
        // 총합이 target 이상일 때
        if (target <= sum)
        {
            ret = std::min(ret, r - l + 1);
            sum -= nums[l];
            ++l;
        }
        // 총합이 target 이하일 때
        else
        {
            ++r;
            sum += nums[r];
        }
    }
    
    return (ret == INT_MAX) ? 0 : ret;
}

 

 

되돌아보기

문제 잘못 이해

target과 정확히 맞는 경우인 줄 알아서 초반에 허튼짓을 했다;

문제를 좀 더 자세히 읽어야겠다.

 

가능한 경우

target과 sum의 두 가지 관계를 고려해 봤었는데, 사실 이전에 어떻게 조건문을 작성하지 머리를 싸매다 '될 수 있는 경우를 작성해 보자! 하고' 정리했었다.

 

정리하고 나니까 좀 더 명확해져서 코드를 작성하기 쉬운 면이 있었다.

다음에는 가능한 경우를 먼저 고려해 보면 좋을 듯하다.

 

개선 코드

좀 더 깔끔한 버전이다.

r은 무조건 마지막까지 증가되어야 함을 이용하여 for문으로 정의했다.

int minSubArrayLen(int target, vector<int>& nums) 
{
    int n = nums.size();

    int l = 0;
    int sum = 0;
    int ret = INT_MAX;

    for (int r = 0; r < n; ++r)
    {
        sum += nums[r];

        while (target <= sum)
        {
            ret = min(ret, r - l + 1);
            sum -= nums[l];
            ++l;
        }
    }

    return ret == INT_MAX ? 0 : ret;
}