#209 Minimum Size Subarray Sum

전우재·2023년 8월 28일

leetcode

목록 보기

11/21

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

문제 조건

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
양수 int 배열 nums와 양수 int target를 받는다.
하위배열 a는 target보다 크거나 같은 최소 길이를 반환한다. 조건을 만족하는 하위 배열의 합계가 없으면 0을 반환한다.

문제 해결

문제 해결 로직

해당 문제는 먼저 배열의 총 합으로 조건을 만족할 수 있는지 확인한다.
target보다 작은 배열의 합을 만족할 수 없다면 0을 반환한다.
target보다 작은 배열의 합을 만족한다면 하위 배열에서 최소값을 뺀다.
2-1. 하위 배열의 합을 구하여 조건을 만족하면 minTotal을 감소한다. 이후 최소값을 빼고 확인하는 과정을 반복한다.
2-2. 합을 구했을 떄 조건을 만족하지 못하면 반복문을 종료한다.

데이터 입력

문제에서 입력이 들어오는 데이터는 양수 int 배열 nums와 양수 int target를 받는다. 해당 조건을 만족하는 조합을 만들기 위해 필요한 변수를 미리 선언해야한다.

sum
현재 배열의 합
currentCount
배열의 총 요소 갯수
deletedIndex
마지막으로 삭제한 배열의 요소 위치

배열의 조건 확인

조건을 만족하기 위한 하위 배열은 해당 배열 값들의 합이 target보다 크거나 같아야 한다.

sum = Arrays.stream(nums).sum();
if(sum < target){
  return 0;
}

하위 배열 업데이트

배열의 모든 값을 더했을 때 target보다 크거나 같다면 하위 배열을 구해볼 수 있다.
없어진 배열을 새로 선언하여 반복하는 것은 배열이 커질 때 마다 복잡도에서 비효율 적이라 생각하였다.
따라서 배열의 제일 작은 값을 제거한 것처럼 0으로 만들어 하위 배열이 조건을 만족하는지 계속 확인할 수 있다.
제일 작은 값을 제거하기 위해 해당 배열은 오름차순으로 정렬해야하고 지울 index도 기억하고 있어야 한다.

// nums 오름차순 정렬
  Arrays.sort(nums);
  
// 합보다 클때까지 배열에서 최소값 제거하기
  while(sum >= target){
    deletedIndex += 1;
    nums[deletedIndex] = 0;
    sum = Arrays.stream(nums).sum();
  }

코드 작성

class Solution {
  public int minSubArrayLen(int target, int[] nums) {
    int sum = 0;
    int currentCount = nums.length;
    int deletedIndex = -1;

    // 모든 합이 target보다는 큰지 확인
    sum = Arrays.stream(nums).sum();
    if(sum < target){
      return 0;
    }

    // nums 오름차순 정렬
    Arrays.sort(nums);
  
   // 합보다 클때까지 배열에서 최소값 제거하기
    while(sum >= target){
      deletedIndex += 1;
      nums[deletedIndex] = 0;
      sum = Arrays.stream(nums).sum();
    }
      
    return currentCount - deletedIndex;
  }
}

복잡도 계산

시간 복잡도
- Arrays.stream(nums).sum()을 사용하면 모든 요소를 한 번 순회하며 합을 계산하므로 O(n)의 시간이 걸린다.
- Arrays.sort(nums)를 사용하여 배열을 정렬하는데 O(n log n)의 시간이 걸린다.
- while의 반복문을 수행하면 최악의 경우 O(n)의 시간이 걸린다.
- 따라서 총 시간 복잡도는 O(n log n) + O(n) + O(n) = O(n log n)이 된다.
공간 복잡도
- 변수는 상수형 데이터만 가지고 있기 떄문에 O(1)의 공간 복잡도를 가진다.

회고

점수를 보려고 했지만 이상한 케이스에서 틀렸다고 표시되었다.
83+28+26+25+25+25+25로 해당 조건을 만족하여 7이 정답인데 8을 기대하고 있다.
해당 코드를 개선하기 위해서 투 포인터나 슬라이딩 윈도우를 사용할 수도 있다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans=nums.length+1;
        int j=0;
        int sum=0;
        
        // nums 배열 순회
        for(int i=0;i<nums.length;i++)
        {
            // 앞에서부터 하위 배열의 합을 구한다.
            sum=sum+nums[i];
            
            // 함계가 target보다 크거나 갇다면
            if(sum>=target)
            {
            	// 하위 배열에서 앞의 값 부터 빼보며 최소 갯수를 구한다. 
                while(sum>=target)
                {
                    sum-=nums[j++];
                }
                ans=Math.min(ans,i-j+2);
            }
        }
        // 같으면 ans가 변경되지 않은 것으로 0 반환
        return ans == nums.length+1 ? 0 : ans;
    }
}