백준 1806번 부분합 | python | 투포인터 알고리즘

문제

링크

풀이

n의 값이 100,000까지 입력가능하기 때문에 기본 탐색 반복문(시간복잡도 : O(N^2))을 사용하면 시간초과로 인해 정답을 맞출 수 없다. 따라서 투포인터를 사용해서 풀이해야만 한다.

포인터 방식은 크게 두가지 방식이 있는데,
(1) 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 방식과 (2) 두 포인터 모두 앞에서 시작하되 속도가 다르게 움직이는 방식이다.

여기서는 후자의 방식으로 투포인터 알고리즘이 진행되며, 풀이 방식은 아래 순서와 같다.

1. left, right 포인터를 모두 0으로 초기화한다.
2. right 포인터를 오른쪽으로 옮겨가면서 right 인덱스를 가진 요소값을 sum 변수에 더한다.
3. sum이 S보다 크거나 같아질때까지 2번을 반복한다.
4. 만약 sum이 S 이상이라면 right가 아닌 left를 한칸씩 옮기며 S보다 작아질 때까지 뺀다.
5. 이 때, right-left 값을 구해서 가장 짧은 길이를 update해준다.

투포인트 알고리즘을 사용하면 left포인터와 right포인터가 각각 배열의 끝에 다다르는데 O(N)의 시간이 걸리므로 이 둘을 합하여도 여전히 O(N)의 시간복잡도를 가지게 된다.

n, s = map(int, input().strip().split())
nums = list(map(int, input().strip().split()))

left, right = 0,0
sum = 0
min_length=1e9

while True:
    if sum >= s:
        min_length=min(min_length,right-left)
        sum -= nums[left]
        left +=1
    elif right == n:
        break
    else:
        sum += nums[right]
        right+=1

if min_length == 1e9:
    print(0)
else:
    print(min_length)