배열에서 두 수의 합이 s가 되는 경우의 수(서로 다른 방향으로 움직이는 투 포인터)

29940번: Sum (acmicpc.net)

 

배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제

 

투 포인터로 어떻게 해결할 수 있을까

 

보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고

 

다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만

 

두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다.

 

그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로 

 

모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[i]는 큰 수부터 시작해야한다.

 

그래서 i = 0,1,2,..,n-1로 움직이면 j = n-1,n-2,n-3,....,0으로 반대편에서 서로 거꾸로 움직이면 된다.

 

i = 0일때, j = n-1부터 시작해서 A[i] + A[j] > s이면, j를 1 감소시키면 A[i] + A[j]가 점점 작아져서 s에 가까워진다

 

그러다가 A[i] + A[j] = s가 되는 순간 counting하고 j를 1 다시 감소시킨다.

 

그러면 A[i] + A[j] < s가 되므로 j를 감소시키는 반복문을 탈출하고 i를 1 증가시켜서 위 과정을 반복한다 

 

i를 1 증가시키면 A[i]가 증가하므로 A[j]는 증가하지 않아야한다. 

 

즉 j를 다시 n-1로 이동시킬 필요 없이 현재 j부터 시작해서 계속 감소시키면 된다.

 

또한 배열의 모든 수가 서로 다르므로 i에 맞는 j는 오직 하나밖에 없다

 

from sys import stdin

n,s = map(int,stdin.readline().split())

A = []

for _ in range(n):
    
    a = int(stdin.readline())
    A.append(a)

j = n-1

count = 0

for i in range(n):

    while i < j:
        
        v = A[i] + A[j]

        if v == s:

            count += 1
            break

        elif v > s:

            j -= 1

        else:

            break

print(count)