부분합 ( 1806 번 )

1806번: 부분합

 

🧠 알고리즘

투 포인터 알고리즘
now_point < s이면 → 오른쪽 포인터를 이동시켜 누적 합 증가
now_point >= s이면 → 현재 길이를 최소값으로 갱신, 왼쪽 포인터 이동

 

🧾 코드

import sys

def _main():
    answer = float('inf')
    l, r , number = -1, -1, 0

    while l <= r:
        if number < s:
            r += 1
            if r == n: # 종료 조건
                break
            number += n_list[r]
        else:
            answer = min(answer, r - l)
            l += 1
            number -= n_list[l]

    return 0 if answer == float('inf') else answer


n, s = map(int, sys.stdin.readline().rstrip().split())
n_list = tuple(map(int, sys.stdin.readline().rstrip().split()))

print(_main())

 

⏱️ 시간 복잡도

_main(n, s, n_list) : 투 포인터 함수 ( 선형 시간 복잡도 )
>> 내부 로직 ( 상수 시간 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )