[LeetCode] 209 - Minimum Size Subarray Sum(java)

https://leetcode.com/problems/minimum-size-subarray-sum/

Minimum Size Subarray Sum - LeetCode

전형적인 윈도우 슬라이딩 문제이다. 난이도가 높지 않고 매우 흔한 형태의 문제이다.

 

 

핵심

사실 이러한 문제는 매우 흔하다. 그래서 정석적인 풀이를 거의 외우듯이 풀어왔다.

아이디어는 간단하다. left와 rigth를 만들어서 현재의 합이 target보다 작으면 rigth를 높여서 sum을 높이고,

크면 반대로 left를 높여서 sum을 줄이는 방식이다.

 

정답 코드

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;
        
        for(int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                if (sum == target) min = Math.min(min, right - left + 1);
                sum -= nums[left++];
            }
        }

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

해설

핵심에서 말했듯이 아이디어가 간단하다.

구체적인 예시를 들어서 설명하자면 target = 7, nums = [2, 3, 1, 2, 4, 3]이라고 하자.

left와 rigth, sum은 0으로 초기화되어 있다.

현재의 sum이 tartget보다 작으니까 rigth를 더하고 1칸 이동한다. 그럼 sum = 2, right = 1이 된다.

이것을 target보다 크거나 같을 때까지 반복한다. 그럼 sum = 8, right = 3까지 증가한 상태이다.

이때 sum이 target 7보다 크기 때문에 이제 left를 올리고 sum을 줄인다. sum = 6, left = 1, right = 3이 된다.

다시 반복하면 sum = 7, left = 2, rigth =4에서 min값이 3으로 업데이트된다.

계속 또 반복하면 sum = 7, left = 4 rigth = 5에서 min 값이 2로 업데이트된다.

 

 

 

배운 점

사실 이러한 문제를 많이 풀어봐서 접근방법은 쉽게 생각할 수 있었다. 

그런데 생각보다 반복문을 컨트롤할 때 어려움을 겪었다.

머리로는 어떻게 해야 할지 알았는데 막상 바로 코드를 작성하니 조건이 한 개씩 어긋나며 틀렸다.

다시 천천히 종이에 적어가며 이를 코드로 구현하니 무사히 통과할 수 있었다.

접근 방법을 바로 생각했더라도 꼼꼼하게 생각하고 접근해야겠다.

이런 건 처음 보는데 아마 대부분 1ms속도로 나와서 나와 비슷한 결과가 나왔을 것 같다. 그래도 신기하다 100%..

요즘 하루 일상의 시작을 운동 후 리트코드를 푸는 것으로 시작한다. 

너무 재미있다. 아마 당분간은 리트코드만 풀 것 같다.