[Python] 백준(BOJ) 2003번: 수들의 합2 - 투포인터 알고리즘

문제

2003번: 수들의 합 2

 

풀이

투포인터 알고리즘을 이용해서 풀었다. 배열의 인덱스를 start, end 두 변수에 저장해서 

원하는 합보다 sum(arr[start:end])가 작아질 경우엔 end를 하나 증가시키고, 같거나 클 경우엔 start를 하나 증가시킨다.

 

주의할점은 루프를 끝내는 시점이다. end가 배열의 길이가 되었을때 루프를 멈춰줬더니, start가 이동하면서 하나씩 빼주는 부분이 생략되어 틀린 답이 나왔다. 또 arr[start]가 범위 초과가 되지 않도록 while not (start == end == N)으로 설정해줬다.  

import sys

N, S = map(int, sys.stdin.readline().split(" "))
arr = list(map(int, sys.stdin.readline().split(" ")))

start = 0
end = 1
count = 0
sum = arr[start]
if sum == S:
    count += 1

while not (start == end == N):
    if sum < S and end < N:
        sum += arr[end]
        end += 1
    else:
        sum -= arr[start]
        start += 1

    if sum == S:
        count += 1


print(count)