[백준] 1806번: 부분합 (투포인터)

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

이 문제는 전형적인 투포인터 알고리즘으로 접근해야하는 문제이다.

 

우선 투포인터 알고리즘 개념을 다시 정리해보자.

투 포인터 알고리즘

투포인터 (Two Pointers)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어 있는 두 리스트의 합집하에도 사용됨. 병합정렬(merge sort)의 conquer 영역의 기초가 되기도 함

 

 

예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기

위 예제 문제는 투포인터 알고리즘의 전형적인 대표 문제이다.

 

어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제이다.

 

1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.

2. 현재 부분 합이 M과 같다면 카운트한다.

3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.

4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.

5. 모든 경우를 확인할 때까지 2~4번 과정을 반복한다.

 

그림과 함께 설명하기

 

 

위와 같은 리스트와 M = 5일 때의 예시를 생각해 보자.

 

• [초기단계] : 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.

• 현재의 부분합 : 1
• 현재 카운트 : 0
• [Step1] 이전 단계에서의 부분합이 1 이므로 end를 증가시킨다.

• 현재의 부분합 : 3
• 현재 카운트 : 0
• [Step2] 부분합이 3 이므로 end를 증가시킨다.

• 현재의 부분합 : 6
• 현재 카운트 : 0
• [Step3] 부분합이 6 이므로 start를 1 증가시킨다.

• 현재의 부분합 : 5
• 현재 카운트 : 1(부분합이 5이기 때문에)
• 이걸 계속 반복하다가 마지막
• [마지막]

• 현재의 부분합 : 5

 

 코드

n = 5 # 데이터의 개수 N
m = 5 # 찾고자하는 부분합 M
 
count = 0
interval_sum = 0
end = 0
 
# start를 차례대로 증가시키며 반복
for start in range(n):
    # end만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]
 
print(count)

 

시간 복잡도

O(N)

 

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝난다.

각각 배열 끝에 도달하는데 O(N) 이라 둘을 합해도 여전히 O(N)이다.

 

 

 

그렇다면 다시 백준 1806 문제를 위와 같은 방법으로 풀어보자.

 

파이썬 소스코드

import sys
input = sys.stdin.readline

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

ans = []
interval_sum = 0
end = 0

for start in range(n):
    while interval_sum < s and end < n:
        interval_sum += a[end]
        end += 1

    if interval_sum >= s:
        ans.append(int(end-start))

    interval_sum -= a[start]

if len(ans) == 0:
    print(0)
else:
    print(min(ans))