투 포인터

개요

만약 어떠한 자연수가 주어지고 이 자연수가 몇 개의 연속된 자연수의 합으로 나타낼 수 있는지 구해야한다고 해보자.
자연수 N(1 <= N =< 10,000,000)가 주어졌을 경우 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 구하라. 시간 제한 2초

예를 들어 15가 주어졌을 경우 15는 1+2+3+4+5, 4+5+6, 7+8, 15로 나타낼 수 있다.

이 문제를 어떻게 풀 수 있을까?
모든 경우의 수를 비교해보는 것도 하나의 방법이지만 이 문제의 경우 데이터의 범위가 1천만이므로 모든 경우의 수를 고려하는 것은 시간 제한을 넘어선다.

이럴 때 O(N)시간복잡도를 가지는 투 포인터 알고리즘을 사용할 수 있다.

투 포인터

투포인터 알고리즘이란 연속된 데이터에서 2개의 포인터를 사용하여 문제를 해결하는 알고리즘이다.
예를 들어 1부터 10까지의 숫자를 말할 때 직접 1, 2, 3…, 10과 같이 말하지 않고 1부터 10까지, 1 <= x <= 10과 같이 나타내곤한다.
투 포인터 알고리즘을 사용하는 대표적인 문제는 위와 같이 특정한 합을 가지는 연속 수열 찾기 문제를 효과적으로 해결할 수 있다

풀이

투포인터는 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 계산하는 것이다.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15에서 start_index와 end_index는 1이다.
sum이 N보다 작기 때문에 end_index를 1씩 증가시킨다.
end_index가 5가 될 때 sum은 15가 된다.
경우의수를 하나 찾았으므로 count를 1증가시킨다.
end_index를 1증가시킨다.

sum은 15 + end_index(6) = 21이 되고 15보다 크니 start_index를 1씩 증가시킨다.

start_index가 4가 될 때 4+5+6은 15이므로 count를 1증가시킨다.

N = int(input())
count = 1
sum = 1
start_index = 1
end_index = 1

while end_index != N:
  if sum == N:
    count += 1
    end_index++
    sum += end_index
  elif sum > n:
    sum -= start_index
    start_index++
  else:
    end_index++
    sum += end_index

print(count)

이와 비슷하게 구간 합 계산 문제가 있다. 예를 들어 배열의 첫 번째부터 마지막까지 요소의 합을 구할 경우 반복문을 돌며 하나씩 더하게 된다. 이렇게 되면 시간복잡도는 O(N)이 된다. 그러나 구간합을 저장하여 사용하게 된다면 O(1)의 시간복잡도로 구할 수 있다.

수 N개가 주어지고 i~j까지의 합을 구해야한다.

n = 5
data = [10, 20, 30. 40. 50]
sum = 0
prefix_sum = [0]


for i in numbers:
  sum += 1
  prefix_sum.append(sum)

left = 2
right = 4

print(prefix_sum[right] - prefix_sum[left])

구간합 배열은 0, 10, 30, 60, 100, 150과 같이 갱신되고 만약 3번째 숫자부터 5번째 숫자까지의 구간합을 구하려면 단순히 prefix_sum[4] - prefix_sum[2]와 같이 구하면 된다.

답은 120이 나온다.

주몽의 명령

```문제 설명 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력 첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 1 6 9 2 7 4 1 5 3 예제 출력 1 2

값 두 개를 더해서 두번째 줄의 입력인 M이 되도록 하는 경우의 개수를 구하는 문제로 데이터를 정렬시킨 뒤 투포인터 알고리즘을 사용하면 해결할 수 있다.  

예를 들어 예제 입력을 정렬해서 보면 1, 2, 3, 4, 5, 7로 만약 시작과 끝 인덱스를 설정한 뒤 더해본다. 1+7은 8로 M 값인 9보다 작다.  
따라서 시작 인덱스를 한 칸 왼쪽으로 이동시킨다. 2+7은 9로 m과 일치한다. 카운트를 1 증가시킨다.  
우리는 정렬을 했기 때문에 이렇게 일치하는 값을 찾은 다음에는 끝 인덱스는 줄어들어야하고 시작 인덱스는 증가시켜야한다.  
3 + 5 = 8이므로 시작 인덱스를 1 증가시킨다. 4+5 = 9 이런 식으로 시작 인덱스와 끝 인덱스가 만날 때까지 반복하면 된다.  

파이썬의 정렬 알고리즘은 최악일 경우 nLogn의 시간복잡도를 가진다.  
데이터의 범위는 15,000으로 약 208,050번의 연산이 수행된다. 이는 일반적인 파이썬 프로그램에서 2초 안에 다룰 수 있으니 정렬해도 문제가 없다.

```py
import sys

input = sys.stdin.readline

n = int(input())
m = int(input())
a = list(map(int, input().split()))
a.sort()
start = 0
end = n - 1
count = 0

while start < end:
    if a[start] + a[end] < m:
        start += 1
    elif a[start] + a[end] > m:
        end -= 1
    else:
        count += 1
        start += 1
        end -= 1

print(count)