LeetCode[ 209 | Python ] Minimum Size Subarray Sum
업데이트:
문제
정수형 배열 nums 와 정수 target이 주어지면 nums의 임의의 부분수열의 합이 target 이상인 것 중 그 수열의 길이가 가장 짧은 수열의 길이를 반환해야하는 문제.
풀이
시도 (시간 초과)
단순하게 부분수열의 합을 구하기 위해 슬라이딩 윈도우를 이용했다.
- 현재 탐색할 윈도우의 크기를 결정하기 위해
nums의 크기만큼 반복문을 수행한다.- 윈도우의 시작 위치를 결정하기 위해
len(nums) - size만큼 중첩 반복문을 수행한다. - 이 때
size는 윈도우의 크기를 고려해 인덱스j가nums의 크기를 초과하지 않도록하기 위함이다.size만큼 부분수열의 합을 구하며 그 합이target보다 큰 경우 바로 size를 출력한다. 이 때 size는 0 부터 시작함을 고려해 1을 더한다.
- 윈도우의 시작 위치를 결정하기 위해
사실상 브루트포스에 가까운 슬라이딩 윈도우를 수행했더니 역시나 10 ** 5에 달하는 입력을 제시간에 처리하지 못했다.
먼저 작성했던 코드의 문제점을 살펴보면, 두번째 중첩반복문에서 size 만큼 크기를 줄여 나아가고 있긴 하지만 결국 sum() 함수로 인해서 반복문을 한번 더 돌고 있는 모습이 보인다.
깊게 생각하지 않아도 최소 시간복잡도 O(N**2)이 소요되는 코드이고, 만 제곱에 달하는 입력을 처리하기는 무리가 있다고 판단되었다.
그렇다면 수정되어야 할 부분은 배열을 탐색해 나아가며 현재의 합을 계속해서 덮어씌워나아가는 부분인데, 이 점을 고려하며 슬라이딩 윈도우를 어떤식으로 수행해야할지 고민했다.
class Solution(object):
def minSubArrayLen(self, target, nums):
for size in range(len(nums)):
for j in range(len(nums) - size):
if sum(nums[j : j + size + 1]) >= target:
return size + 1
return 0
해결
- 배열의 시작 부분을 결정할
l을 초기화한다. - 현재의 합을 저장할
cur을 초기화한다. - 가장 짧은 부분수열의 길이를 저장할
min_val을 저장한다. nums의 크기만큼 반복문을 수행한다 이 때 인덱스로 사용할 수는 부분 수열의 끝 부분을 결정할r이다.- 현재의 합
cur에 수열의 끝r이 가리키는 수를 더한다. (부분 수열을 추가한다.) - 만약
cur이target이상이라면, 현재 수열의 길이를 저장하고 가장 앞 부분l을 뒤로 민다.
- 현재의 합
- 반복문을 모두 수행하면
min_val을 반환한다. 이 때 초기화 값과 값이 동일하다면 0을 출력한다.
브루트포스를 통해 슬라이딩을 수행했던 이전 코드와 달리 투포인터를 통해 슬라이딩 윈도우를 구현했다.
결국 부분수열의 크기가 늘어난다는 것은 nums의 값을 하나씩 더해간다는 것이고, 크기가 줄어드는 것은 nums의 앞부분의 값을 하나씩 빼나아간가는 것을 떠올렸기 때문이다.
투포인터라는 생각 때문에 처음은 while 문으로 구현하려했는데, r 값은 항상 커져야 한다는 점을 깨달아 좀 더 사용하기에 안정적인 for 문을 사용했더니 구현하기에 한결 수월해졌다.
결과적으로 189ms의 수행속도와 23.5MB 메모리 사용으로 나름 준수한 결과로 풀이해낼 수 있었다.
class Solution(object):
def minSubArrayLen(self, target, nums):
l = 0
cur = 0
min_val = float('inf')
for r in range(len(nums)):
cur += nums[r]
while cur >= target:
min_val = min(min_val, r - l + 1)
cur -= nums[l]
l += 1
return min_val if min_val < float('inf') else 0
생각 & 정리
투포인터를 떠올린 나도 장하다 !라고 생각했는데, 항상 기발하고 좋은 생각을 떠올리는 사람들이 있다.
문득 떠올린 이분 탐색은 정렬되지 않은 배열이라서 사용할 수 없다고 생각했었는데, 이를 구현한 사람이 있었다. 그 좋은 생각의 흐름은 다음과 같았다.
현재의 합 cur을 계속해서 저장해 나아가며,
cur - target 을 통해 cur에서 어떤 값을 빼야지 target과 가까워 질 수 있는지 이분 탐색을 통해 인덱스를 찾아 뺀다.(내 코드의 l에 해당하는 부분이다.)
이분탐색의 조건인 정렬이 점점 늘어가는 현재 부분수열의 합이 될 지는 떠올리지 못했는데, 정말 대단하다는 생각이 들었다.
연속으로 투포인터 문제를 풀어가다보니 시각이 좁아지지 않을까 하는 걱정이 들었지만, 환기가 되는 풀이였다!
댓글남기기