합이 S와 같거나 큰 subarray의 최소 길이 구하기

Smallest Subarray With a Greater Sum (easy)

리트코드의 이지 난이도 문제풀이다.

 

문제 설명

앞의 최대 합 서브어레이 구하기 응용인데,

다른 점은 if를 while로 변경해주는 점이다. (하나의 값을 더했을 때, S값을 넘어버릴 수 있기 때문이다.)

또 나는 길이를 length 변수로 따로 선언했는데,

window_end-window_start+1로 바로 구할 수 있다.

알고리즘 풀이에는 루프를 돌면서 증가시켜줘야 하는 값 갯수는 최소화 시켜주는게  맞다고 생각.

아니면 효율성은 약간 떨어지더라도, 코드로 뽑아내는(함수로) 방법도 있음.

파이썬 풀이

def smallest_subarray_sum(s, arr):
  window_sum = 0
  min_length = math.inf
  window_start = 0
  def length():
    return window_end - window_start + 1

  for window_end in range(0, len(arr)):
    window_sum += arr[window_end]  # add the next element
    # shrink the window as small as possible until the 'window_sum' is smaller than 's'
    while window_sum >= s:
      min_length = min(min_length, length())
      window_sum -= arr[window_start]
      window_start += 1
  if min_length == math.inf:
    return 0
  return min_length