백준 2003번 파이썬 문제풀이(수들의 합 2)

---

이 문제는 전형적인 투포인터 문제이다. 투포인터로 풀지 않으면 파이썬으로는 시간초과 발생한다. 그나마 파이파이3로 제출하니 시간초과는 발생하지 않았는데 이 기회에 투포인터도 공부할 수 있었다. 2가지 코드 모두 공유하겠다. 

 

1. 투포인터 풀이

N, M = map(int, input().split())
array = list(map(int, input().split())) + [0]  # 인덱스 오류 방지를 위해 한칸 뒤에 의미없는 0값을 추가

s = 0  # 첫번째 포인터
e = 0  # 두번째 포인터

total = array[0]  # 구간합을 저장할 변수 첫번째 값을 넣어 놓는다.
count = 0  # 횟수를 셀 변수
while e < N:  # 끝 인덱스가 N 전까지

    if total == M:  # 만약 구간 합이 M이라면
        count += 1  # 개수 1개 추가
        e += 1  # 두번째 포인터를 한칸 뒤로옮겨준다.
        total += array[e]  # 구간 합에 해당 값을 추가
    elif total < M:  # 만약 구간합이 M보다 작다면
        e += 1  # 두번째 포인터 한칸 뒤로 옮겨준다.
        total += array[e]  # 구간 합에 해당 값을 추가
    else:  # 만약 구간합이 M보다 크다면
        total -= array[s]  # 구간합에서 첫번째 포인터가 가리키는 값을 제거한 후
        s += 1  # 첫번째 포인터 한칸 뒤로 이동

print(count)

 

2. 투포인터 for문과 while문 사용

N, M = map(int, input().split())
array = list(map(int, input().split()))

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(N):

    # end를 가능한 만큼 이동시키기
    while interval_sum < M and end < N:
        interval_sum += array[end]
        end += 1

        # 부분합이 m일때 카운트 증가
    if interval_sum == M:
        count += 1

    interval_sum -= array[start]  # 위의 while내부의 조건때문에 반드시 interval >= m 상태로 while문을  빠져 나온다.

print(count)

 

2. 나의 풀이

N, M = map(int, input().split())
array = list(map(int, input().split()))

s = 0
e = N - 1
count = 0
sum_ = sum(array[:])
temp_sum = sum_
while True:

    if sum_ == M:
        count += 1

    if s == N - 1:
        break

    sum_ -= array[e]
    e -= 1

    if s > e:
        sum_ = temp_sum - array[s]
        temp_sum = sum_
        s += 1
        e = N - 1

print(count)