[Java] 209. Minimum Size Subarray Sum

문제 파악

 

정수 배열 nums 와 양수 target 이 주어진다

 

부분 집합의 합이 target 과 동일하거나 이상 값을 갖는 최소 길이를 반환해야한다.

 

없다면, 0을 반환한다.

 

---

풀이

1️⃣ 투 포인터 풀이

💡 떠오른 Idea

투포인터 방식으로 부분합을 구하다가, target과 동일하거나 그 이상 값이 되면 기록한다.

그리고, 왼쪽 포인터를 옮긴 뒤에 다시 탐색을 한다.

 

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = 0;
        while (right <= nums.length) {
            if (sum < target) {
                if (right == nums.length) {
                    break;
                }
                sum += nums[right++];
            } else {
                ans = Math.min(ans, right - left);
                sum -= nums[left++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

 

의도한 대로, 부분합이 target 이상이면 left 포인터를 이동해서 다시 whlie 문을 실행하게끔 하였다.

 

만약 right가 배열 끝에 도달했는데도, target 보다 작다면 더 더할 수가 없으르모 while 문을 그만 실행해도 된다.

 

결과

 

 

2️⃣ 이분탐색 풀이

O(NlogN) 풀이 방법으로 해결해보라고 하길래 생각해보았다.

 

보통, O(NlogN) 은 이분 탐색이므로 자연스럽게 이분탐색 풀이를 떠올려보았다.

 

이분탐색을 사용하려면 배열이 정렬되어있어야 하고,

 

그렇다면 이 문제에 사용할 수 있는 방법은 구간 합 알고리즘을 통해 배열을 오름차순으로 만들어야겠다고 생각했다.

 

구간 합 알고리즘

 

배열 [ 16, -5, -11, -15, 10, 5, 4, -4 ] 가 있다고 할 때,

 

누적합 배열을 구하면

 

[ 16, 11, 0, -15, -5, 0, 4, 0 ] 이 된다.

 

예를 들어 index가 1번째 원소부터 5번째 원소까지의 구간 합을 구해야 한다면

 

arr[1] + arr[2] + arr[3] + arr[4] + arr[5] = (-5) + (-11) + (-15) + 10 + 5 = -16이다.

 

누적합 배열을 이용한 구간합 알고리즘을 활용하면 sum[5] - sum[0] = -16으로 단 한번의 연산으로 구간 합을 구할 수 있다.

 

💡 정리하면, 배열 a ~ b 까지의 구간합을 구할 때, 누적합 배열의 sum[b] - sum[a-1] 로 구할 수 있다.

 

구간 합 알고리즘과 이분탐색을 풀이에 적용

그래서 내가 떠올린 방식은, 구간합 배열을 구하고 

 

a~b 까지의 합을 구할 때,

 

for문을 순회하면서 a를 고정시키고 b-a가 target 이상을 만족하는 값이 존재하면 

 

구간합이 target이상이 되는 부분이 존재한다는 의미이고, 그 조건을 만족했을 때 값을 갱신하는 방식을 선택했다.

 

class Solution {
        public int minSubArrayLen(int target, int[] nums) {
        int[] sum = new int[nums.length + 1];
        int ans = Integer.MAX_VALUE;

        // 누적합 배열 만들기
        for (int i = 1; i < sum.length; i++) {
            sum[i] = nums[i - 1] + sum[i - 1];
        }

        // a~b 의 합이 target 보다 큰 부분 구하기
        for (int i = 0; i < sum.length - 1; i++) {
            // fixed 는 sum[a]에 해당하는 값 
            int fixed = sum[i];

            // sum[b]-sum[a] = 구간합 >= target 이 되는 부분 찾기
            int find = target + fixed;

            // 이분탐색
            int left = i + 1, right = sum.length - 1;
            while (left < right) {
                int mid = (left + right) / 2;
                if (find <= sum[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            if (sum[left] >= find) {
                ans = Math.min(ans, left - i);
            }

        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

 

이분탐색을 구현하는 방법은, 사람마다 약간씩 다르니

 

내가 제시한 논리와 비슷한 방식으로 이분탐색을 구현하면 될 것 같다.

 

결과

 

 

3️⃣ Arrays.binarySearch() 활용

 

아래 코드는 자바에서 제공하는 이분탐색 메서드인, Arrays.binarySearch() 를 사용해서 풀어보았다.

 

참고로, 해당 key를 찾으면 그 위치를 리턴하고, 그렇지 않으면 -Insertion point-1 값을 리턴한다.

insertion point : 오름차순 정렬했을 때, 삽입할 수 있는 위치

 

import java.util.*;
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int[] sum = new int[nums.length + 1];
        int ans = Integer.MAX_VALUE;

        // 누적합 배열 만들기
        for (int i = 1; i < sum.length; i++) {
            sum[i] = nums[i - 1] + sum[i - 1];
        }
        // a~b 의 합이 target 보다 큰 부분 구하기
        for (int i = 0; i < sum.length - 1; i++) {
            // fixed 는 sum[a]에 해당하는 값 
            int fixed = sum[i];

            // sum[b]-sum[a] = 구간합 >= target 이 되는 부분 찾기
            int find = target + fixed;

            int result = Arrays.binarySearch(sum, find);

            if (result > 0 && result > i) {
                ans = Math.min(ans, result - i);
            } else {
                int idx = -result - 1;
                if (idx < sum.length) {
                    ans = Math.min(ans, idx - i);
                }
            }

        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

 

결과

---

📖 회고

 

왜 효율적인 O(N) 풀이를 냅두고 O(NlogN) 풀이를 요구하는지 궁금하긴 했다.

 

LeetCode 의 커뮤니티를 보니, 간혹 면접관이 다른 방식 접근을 물어보는 경우가 있다고 한다.

 

알고리즘 문제를 여러가지 접근법으로 풀어보는 습관이 지금까지는 없었는데, 깊게 고민해보는 습관을 들여야겠다.