LeetCode Top Interview 150) Minimum Size Subarray Sum

Question

Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

---

---

정렬되지 않은 정수 리스트nums가 있고 nums 내에서 연속하는 리스트 합이 target보다 크거나 같은 부분이 있는지 확인합니다. 그리고 만족하는 연속하는 리스트들 중

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left_idx = 0
        min_len = 10**5+1
        sum_val = 0

        for right_idx,n in enumerate(nums):
            sum_val += n
            while sum_val >= target:
                min_len = min(min_len,right_idx - left_idx + 1)
                sum_val -= nums[left_idx]
                left_idx += 1
        
        return min_len if min_len!=10**5+1 else 0

• left_idx : 연속하는 하위 리스트의 가장 왼쪽 인덱스 변수입니다.
• min_len : 하위 리스트들 중 최소 길이를 저장하는 변수입니다. 조건에서 나올 수 있는 최대길이보다 크게 초기화합니다.
• sum_val : 특정 하위 리스트의 합입니다.
• nums를 순차 탐색하며 sum_val에 원소 값을 더합니다.
  • 합이 target 이상이 되면 현재 최소 길이와 비교합니다.
  • 하위 리스트의 왼쪽 값을 하나씩 없애가며 target보다 작아질 때 까지 최소 길이를 업데이트합니다. 쉽게 말해 오른쪽으로 하나씩 늘려가며 왼쪽은 target보다 작아지기 전까지 하나씩 줄여가며 최소 길이를 만듭니다.
• 반복문이 끝나면 최소 길이를 반환합니다. 단 처음 초기화 값이 유지되었다면 만족하는 하위 리스트가 없는 것이므로 0을 반환합니다.

---

처음에는 while문으로 두 개의 양 옆 인덱스를 사용하는 방법으로 접근했습니다. 그런데 이 방법은 두 가지 해결하기 힘든 문제가 생깁니다.

• while문 반복 조건에서 비효율적인 인덱스 확인이 필요하다.
  • while문이기 때문에 왼쪽이 오른쪽을 넘어선 안되는 부분을 추가해주고, 오른쪽 인덱스가 최대 길이보다 작아야 한다는 점을 넣어야 합니다.
  • 하지만 이런 방식은 처음이나 마지막 인덱스를 확인할 때 많은 예외가 불러와집니다. 예외문을 만이 사용하게 되고 애초에 인덱스끼리 많은 조건을 가지게 되므로 가독성도 떨어집니다.
• 오른쪽 인덱스와 왼쪽 인덱스 중 어느 것을 조정할 지 어떻게 기준을 잡든 코드에 불필요한 요소가 많아진다.
  • 만약 target보다 값이 부족할 때 오른쪽을 늘려가는 방식이라면, target보다 작아질 때 왼쪽을 움직입니다.
    • 이 때 전체 while문 조건인 인덱스 조건을 다시 써서 확인하게 됩니다.
    • 합이 존재하지 않는 경우 또다시 예외문을 내부적으로 두게 됩니다.

이 외에도 분명 문제가 더 있었을텐데 포기하고 for문으로 코드를 작성했습니다.. 방향 전환을 해서 다행이란 생각이 어후...

앞으론 연속되는 하위 리스트를 확인하는 상황에선 for문을 우선적으로 생각하는 방식을 사용하도록 노력해야겠습니다. 인덱스 변수도 덜 쓰고 마지막 원소 확인에서 예외 상황도 덜 나오고 좋네요. (왜 그 동안 while문을 자주 사용했지..?)