[Leetcode Top Interview 150] 209. Minimum Size Subarray Sum

문제링크

• 자연수 배열인 nums와 자연수 target이 주어짐
• 합이 target이상인 subarray중 가장 작은 길이의 subarray를 리턴하라

 

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

 

1. 접근법

• subarray면 연속된 자연수 원소들
• 길이가 작은것부터 리턴해야 하므로
• 작은 길이의 subarray들 생성 target보다 큰지 체크
• subarray로 +1크기의 subarray 생성 가능

 

2. 의사코드

while(subarray 크기가 nums의 길이보다 작거나 같다면) {
   for(i 0부터 nums.length까지) {
        if (i 인덱스값이 target보다 크거나 같으면) {
            return subarray 크기
        }

        if (i 인덱스가 nums.length - subarray 크기보다 작다면) {
            i 인덱스에 subarray 배열 합을 저장함
        }    
    }
        
    subarray 크기++;
}

return 0;

• for 문의 i는 i인덱스를 시작점으로  subarray 크기까지 합을 저장함
• 다음 while문이 돌면 배열의 i값을 검사하여 target보다 크거나 같으면 해당 subarray 크기가 해가 된다

 

3. 구현 코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {        
        int[] curSubElemArr = nums.clone();
        int curSubElemCount = 1;

        while (curSubElemCount <= nums.length) {
            for (int i = 0; i < nums.length; i++) {
                if (curSubElemArr[i] >= target) {
                    return curSubElemCount;
                }

                if (i < nums.length-curSubElemCount) {
                    curSubElemArr[i] += nums[i+curSubElemCount];
                }
            }

            curSubElemCount++;
        }

        return 0;
    }
}

• 의사코드와 같이 작성하였다
• 시간복잡도가 O(n^2)으로 좋지 않아 time limit exceeded로 실패하였다 (길이가 짧은 input은 통과했는데ㅠㅠ)

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n^2) - n번 n개의 원소를 반복하므로
• 공간복잡도 : O(1) - n개 원소를 돌아도 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘

 

5. 개선점

모르겠다..

 

6. 회고

이번엔 블로그가 아닌 유명 youtube인 neetcode의 설명을 듣고 풀었다 

구현은 직접하려 설명까지 들었는데 슬라이딩 윈도우를 투포인터로 구현하는 문제였었다 

 

class Solution {
    public int minSubArrayLen(int target, int[] nums) {        
        int left = 0;   
        int right = 0;
        int subSum = nums[0];
        int ans = nums.length+1;

        while (left <= right && right < nums.length) {
            if (subSum >= target) {
                if (ans > right-left) {
                    ans = right-left;
                }

                subSum -= nums[left++];
            } else {
                if (right == nums.length-1) break;
                subSum += nums[++right];
            }
        }

        return ans == nums.length+1 ? 0 : ans+1;
    }
}

(출처 : https://www.youtube.com/watch?v=aYqYMIqZx5s&t=1s&ab_channel=NeetCode)

 

• 왼쪽부터 오른쪽까지 포인터의 subarray 합이 target보다 크거나 같다면
  • right-left값이 ans보다 크다면 ans 갱신
  • subarray합을 left포인터 값만큼 줄여보기
    • left포인터++ 
• 왼쪽부터 오른쪽까지 포인터의 subarray 합이 target 작다면
  • subarray합을 늘리기
    • right포인터++
    • right 포인터의 값을 subarray 합에 더하기

 

유형을 모르니 고생만하고 풀지를 못했다ㅜㅜ