January 15, 2023

1806번: 부분합

문제 요약

• 길이 N짜리 수열 내에서 합이 S이상인 구간 중 가장 짧은 구간의 길이 출력
• 10 ≤ N ≤ 100,000, 0 < S ≤ 100,000,000
• 시간 제한 : 0.5초

풀이

from sys import maxsize

N, S = map(int, input().split())
num_list = list(map(int, input().split()))
interval_sum = 0
end = 0
result = maxsize

for start in range(len(num_list)):
    while (interval_sum < S and end < N):
        interval_sum += num_list[end]
        end += 1

    if (interval_sum >= S):
        result = min(result, end - start)

    interval_sum -= num_list[start]

if (result == maxsize):
    print(0)
else:
    print(result)

• 투 포인터 이용

시간 복잡도

• 투 포인터 알고리즘 O(N)