?백준 | 수들의 합 2

백준 수들의 합 2

아래와 같이 브루트 포스(Brute Force)로 접근하면, O(N^2)의 시간 복잡도를 갖게 된다.
그런데 문제의 시간 제한이 0.5초이기 때문에, 시간 초과가 뜬다.

# 오답(시간 초과)


import sys

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

ans = 0
for i in range(n):
    for j in range(i, n):
        sub_sum = sum(arr[i:j + 1])
        
        if sub_sum == m:
            ans += 1
        elif sub_sum > m:
            break

print(ans)

투 포인터(Two Pointer)를 활용하면, 아래와 같이 시간 복잡도가 O(N)인 코드를 짤 수 있다.

접근 방향성은 다음과 같다.

[1] current_sum == m인 경우
문제 조건을 만족하는 경우이므로, count 값을 1만큼 증가시킨다.

그리고 배열의 값이 30,000 미만의 자연수이므로, end의 값이 증가하면 무조건 m보다 커질 수밖에 없다. 따라서 현재 start 값을 current_sum에서 빼고, start 값을 1만큼 증가시켜 새로운 시작점을 만들어줘야 한다.

[2] current_sum > m인 경우
current_sum에서 현재 start에 해당되는 값을 뺀 값부터 다시 탐색해야 한다.

[3] current_sum < m인 경우
current_sum이 m이 되려면 m - current_sum만큼의 값이 더 필요하다는 의미이므로, end 값을 1만큼 증가시키고, arr[end]를 current_sum에 더해준다.

이때, end += 1 후의 end 값이 n보다 크거나 같다면, 범위를 벗어나는 경우이므로, 그렇지 않은 경우만 위의 로직을 실행해야 한다.

코드는 다음과 같다.

# 정답


import sys

# 입력
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

# 투 포인터(Two Pointer)
# 부분 합이 m이 되는 횟수 계산
start, end = 0, 0
current_sum = arr[end]
count = 0

while end < n:
    if current_sum == m:
        count += 1

        current_sum -= arr[start]
        start += 1
    elif current_sum > m:
        current_sum -= arr[start]
        start += 1        
    elif current_sum < m:
        end += 1

        if end < n:
            current_sum += arr[end]

# 출력
print(count)