리트코드 - 209. Minimum Size Subarray Sum

리트코드 - 209. Minimum Size Subarray Sum

출처 - https://leetcode.com/problems/minimum-size-subarray-sum/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 양수로 이루어진 정수 배열 nums와 양수 정수 target이 주어집니다. 목표값 target 이상의 합을 가지는 부분배열(subarray)의 최소 길이를 반환하세요. 만약 그러한 부분배열이 없으면 0을 반환하세요.

 

의사코드

부분배열의 합 = 0 왼쪽 포인터 = 0 최소값 = 큰 수 반복문 시작(nums 배열 순회)     부분 배열의 합을 더함     반복문 시작( 부분배열의 합 >= target)         부분배열의 합 - 배열[왼쪽 포인터]         최소값 = 큰수와 (현재까지 인덱스 - 왼쪽 포인터 + 1)         왼쪽 포인터 +1     반복문 종료 반복문 종료 if 왼쪽 포인터가 0이라면     0 리턴 최소값 리턴

풀이코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int arraySum = 0;
        int left = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            arraySum += nums[i];

            while (arraySum >= target) {
                min = Math.min(min, i - left + 1);
                arraySum -= nums[left];
                left++;
            }

        }

        if (left == 0) {
            return 0;
        }

        return min;
    }
}

코드설명

이 문제는 슬라이드 윈도우 기법을 사용해서 풀었다.

슬라이드 윈도우이란 쉽게 말해 관심사에만 초점을 맞추는 기법이다.

 

만약 배열에서 인접한 세 수의 합이 제일 큰 것을 찾는 경우, 

1,2,3번째 배열의 합을 이미 더해놓고 한 칸씩 옆으로 이동하며 가장 오래된 값을 버리고 다음 값을 더하여 갱신하는 방법이다.

마치 큐(Queue)에서 FIFO인 것과 같지만 배열의 크기가 고정되어 있다는 점이 큐와는 다른 점이다.

 

위 코드에서는 인접한 수의 합(arraySum)이 목표값(target)보다 커진 경우 이 때 배열의 길이를 최소값(min)으로 저장한다.

그리고 처음값을 빼고, left를 1 더한다.

만약 target값보다 또 크다면 left를 또 더하는 식이다.

 

이대로 끝나지않고 배열을 계속 탐색하며 arraySum이 target보다 커졌으면 left를 또 줄여보며 min 값을 찾는다.

최종적으로 left 값이 이동하지 않은 경우 배열의 총합보다 target이 큰 것이므로 0을 반환하고, 아닌 경우 min을 반환한다.

 

배열의 총합이 target이랑 완전히 같으면 0이 반환되는거 아니냐는 반례가 있다고 생각할 수 있지만..

잘 보면 while문에서 총합이 같아도 left를 한 번 이동시킨다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

문제를 처음 접하고 수업에서 배운 슬라이드 윈도우 기법을 그냥 사용해봤다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = 1;

        while (n <= nums.length) {
            int arraySum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i < n) {
                    arraySum += nums[i];
                } else {
                    arraySum = arraySum - nums[i - n] + nums[i];
                }
                
                if (arraySum >= target) {
                    return n;
                }
            }
            n++;
        }
        return 0;
    }
}

하지만 시간초과...

 

while문을 제일 바깥에 쓰는 건 언제나 찝찝하기도 하고, 그안에 for문이 또 있는 건 더 뭔가 껄끄럽다.

위 코드는 예외 케이스를 통과하지 못했는데, 배열 값이 엄청나게 많았던 것으로 기억한다.

 

처음에는 n이 1인 경우, n이 2인 경우, ....., 늘려나가며 최소값을 n을 찾고자 했으나 역시나 n^2 만큼의 시간이 걸리니 시간초과가 났다.

 

투 포인터와 슬라이드 윈도우  

그래서 이번 문제에서는 슬라이드 윈도우도 투 포인터와 짬뽕을 하면 가능할 것 같다는 생각으로 정답 코드를 만들었다.

기법은 차이가 나지만 두 개의 포인터를 통해 관심사를 이동시킨다는 점에서 개념이 매우 비슷한 것 같다.

 

같은 코드 메모리 차이?

같은 코드를 여러번 돌려봤는데 메모리가 어떤건 53.8MB이 나왔고, 어떤건 55.6MB가 나왔다.

메모리가 적은건 88%에 해당하고, 높은건 61%에 해당한다...컴퓨터 성능 차이인가

 

다른코드는 어떤가 살펴봤는데 특별히 아이디어가 다른 걸 찾기는 어려웠다.

정리

슬라이드 윈도우 기법으로 문제 풀기