문제 25
순서 쌍 찾기
정수 수열 $A_1, A_2, \cdots, A_N$과 정수 $X$가 주어진다.
$A_i+A_j=X$를 만족하는 순서쌍 $(i, j)$의 개수를 구하라. $(1 \le i < j \le N)$
입력
첫 번째 줄에 두 정수 $N$, $X$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; -2 \cdot 10^9 \le X \le 2 \cdot 10^9)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9; A_1<A_2<\cdots<A_N)$
출력
조건을 만족하는 순서쌍 $(i, j)$의 개수를 출력한다.
예제 입력 1
7 10 -2 1 3 4 6 7 12
예제 출력 1
3
공식 해설
모든 쌍을 확인하면 $N\le100\,000$에서 너무 많은 비교가 필요하다. 수열이 이미 증가하므로 양 끝의 합을 보고 정답이 될 수 없는 원소를 하나씩 제외한다.
가장 작은 원소에 포인터 $l=1$, 가장 큰 원소에 포인터 $r=N$을 놓는다. $l<r$인 동안 합 $A_l+A_r$을 $X$와 비교한다.
합이 작으면 $A_l$은 현재 남은 어떤 원소와 더해도 $X$가 될 수 없다. 따라서 $l$을 하나 늘린다. 합이 크면 $A_r$은 현재 남은 어떤 원소와 더해도 $X$보다 크므로 $r$을 하나 줄인다.
합이 같으면 정답 쌍 하나를 찾았으므로 답을 늘리고 두 포인터를 모두 안쪽으로 옮긴다. 모든 값이 서로 다르므로 $A_l$의 짝이 될 수 있는 값은 $A_r$뿐이고, $A_r$의 짝도 $A_l$뿐이다. 따라서 두 원소를 모두 제외해도 다른 정답을 놓치지 않는다.
각 단계가 적어도 하나의 원소를 제외하므로 시간복잡도는 $O(N)$이다. 수열을 저장하는 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
수열을 vector<int>에 저장하고 $0$ 기반 인덱스 두 개를 양 끝에서 시작한다. 반복 조건은 l < r이며, 합이 같은 경우에는 답을 늘리고 두 인덱스를 모두 움직인다. 합과 목표값은 long long으로 비교해도 된다.
C 구현
정렬된 int 배열에 l=0, r=N-1을 두고 l < r인 동안 합을 비교한다. 두 원소의 합은 $[-2 \cdot 10^{9}, 2 \cdot 10^{9}]$이므로 int 범위에 들어간다.
Python 구현
이미 정렬된 리스트를 양 끝에서 좁힌다. l < r인 동안 합이 $X$보다 작으면 $l$만 늘리고 크면 $r$만 줄인다.
Java 구현
int[] 원소를 사용하고 두 원소를 더할 때 (long)a[l] + a[r]로 비교한다. l < r 조건은 서로 다른 위치를 선택하도록 보장한다.
Rust 구현
Vec<i32>의 두 인덱스를 이동한다. $N=1$일 때도 l < r 조건으로 검사 없이 끝나며, $r$을 줄이는 연산은 이 조건 안에서만 하여 usize 언더플로를 피한다.
JavaScript 구현
이미 정렬된 숫자 배열에 두 인덱스 l=0, r=n-1을 두고 l < r인 동안 처리한다. 합이 작으면 l++, 크면 r--, 같으면 답을 늘리고 둘 다 움직인다.
원소 합의 절댓값은 $2\cdot10^9$ 이하이므로 Number로 정확하다.