Week 1-2. [Sliding Window] 209. Minimum Size Subarray Sum (Java)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Minimum Size Subarray Sum - LeetCode

주어진 배열로 이루어진 subarray 의 요소 합이 target 보다 크거나 같을 때, subarray의 최소 길이를 반환하라.

• 입력
  • nums | int array := 양의 정수 배열, | nums | ∈ [1, 10^5]
  • target | int := 부분 배열이 target보다 크거나 같아야 한다, | target | ∈ [1, 10^9]
• 출력
  • k | int := 조건을 만족하는 부분 배열의 최소 길이
• 조건
  • | numbers[i] | ∈ [-1000, 1000]
  • subarray란 연속적인 부분 배열이다.

 

🔎 어떤 식으로 접근했는가?

주먹구구식으로 subarray의 길이를 1부터 N까지 늘려가며, 합이 target 이상일 때 중단하려 생각했다. 

subarray의 길이를 i라고 한다면, 각각의 i에서 합을 구하기 위해 Sliding Window 알고리즘을 사용할 것이다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

numbers의 최대 길이가 100,000이므로 O(N^2)으로 구현한다면 터질것이다..

우선은 직관적으로 생각나는 방법인, 2중 for문으로 구현한 뒤 단일 for문으로 개선해 볼 것이다.

📝 의사 코드

sum = 0
for (i=1부터, 배열길이까지, 1씩 증가) {
	lp = 0
    rp = i
    
	for (j=0부터, rp까지, 1씩 증가) {
    	sum에 nums[j] 누적
    }
    
    while (rp가 nums.length보다 작은 동안) {
    	sum에 nums[rp] 더하기
        sum에 nums[lp] 빼기
        if (sum이 target보다 크거나 같으면) {
        	sum 반환
        }
        rp++
        lp++
    }
    sum을 0으로 초기화
}

 

🎯 구현 코드

역시나 Time Limit Exceeded가 발생한다.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;

        for (int i=1; i<=nums.length; i++) { // i는 subarray 길이
            int lp = 0;
            int rp = lp + i;
            for (int j=lp; j<rp; j++) {
                sum += nums[j];
            }
            if (sum >= target) {
                return i; // 최소 subarray 길이 반환
            }
            // Sliding Window
            while (rp < nums.length) {
                sum -= nums[lp];
                sum += nums[rp];
                if (sum >= target) {
                    return i; // 최소 subarray 길이 반환
                }
                lp++;
                rp++;
            }
            sum = 0;
        }
        return 0;
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

외부 루프에서 i는 1부터 nums.length까지 순차적으로 증가한다. 따라서 외부 루프는 O(N)번 수행된다.

내부 루프에서 lp와 rp는 각각 최대 O(N)번 움직일 수 있다. 따라서 전체 코드의 시간복잡도는 O(N^2)이다.

 

✍️ 성능 회고

모든 subarray를 순회하며 합을 계산하는 방식이므로 효율적이지 않은 알고리즘이다.

 

💡 무엇을/어떻게 개선할 수 있을까?

30분 이상 고민해 보았으나 모든 subarray를 순회하는 방식 이외에는 도저히 생각나지 않아 해답을 참고했다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

우선 rp를 0으로 두고, rp만 1씩 늘려가며 (lp는 고정) 0번 인덱스부터 rp번 인덱스까지의 합이 target보다 커지는 시점을 찾는다.

0부터 rp까지의 합이 sum보다 크다면, 이제 lp를 움직인다.

lp를 0부터 1씩 늘려가며 sum에서 nums[lp]를 뺀다. 이때, sum이 target보다 크다면 ans의 값을 갱신한다. (rp-lp)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, lp = 0, rp = 0, ans = Integer.MAX_VALUE;
        while (rp < nums.length) {
            sum += nums[rp]; // ✅ 오른쪽 창문을 늘리며 sum이 target보다 커지는 시점을 찾는다.
            rp++;
            while (sum >= target) {
                ans = Math.min(ans, rp-lp); // 중간중간 조건이 만족할 때마다, 해당 시점의 서브 배열의 길이를 체크하며 최솟값을 찾는다.
                sum -= nums[lp]; // ✅ 왼쪽 창문을 닫으며 조건을 만족하는지 체크한다.
                lp++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

외부 while문은 O(N)의 시간 복잡도를 가진다.

내부 while문은 sum의 조건을 충족시킬 때에만 실행된다.

따라서 전체 코드의 시간 복잡도는 O(N)이다.

 

느낀 점

처음에 subarray의 정의를 착각하여 더 효율적인 코드를 생각하지 못했다.

subarray는 "연속적인" 배열을 의미하는데, 연속적이지 않은 부분 배열도 가능한 것으로 잘못 이해했다. 

문제를 정확히 이해하는 것이 가장 중요함을 다시 한번 깨달았다.