[백준 3273] 두 수의 합

백준 3273번 - 두 수의 합

백준 3273번

❓ 문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. 
ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 
자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.  

입력
첫째 줄에 수열의 크기 n이 주어진다. 
다음 줄에는 수열에 포함되는 수가 주어진다. 
셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)  

예제 입력 1 
9
5 12 7 10 9 1 2 3 11
13
예제 출력 1
3

---

✏️ 풀이

for 문을 2개 중첩해서 brute-force로 모든 경우의 수를 조사해버리면, TLE(Time Limit Exceeded)가 난다.
우리는 조사해야 할 범위가 100,000이기 때문에 for문 중첩 없이 해결해야한다.

그렇다면 어떻게 해결할까?
Two Pointer 알고리즘을 이용한다.
Two Pointer 알고리즘은 두 개의 포인터를 이용하여 1차원 배열에서 원하는 결과를 얻을 수 있는 알고리즘이다.

1. 배열을 sort함(오름차순)
2. 각각의 포인터는 배열의 처음과 끝을 가리킴
3. sum = arr[처음 포인터] + arr[끝 포인터]
4. 만약 sum과 찾는 값이 같다면 끝 포인터-=1 하고 count 증가
5. sum이 찾는 값보다 작다면 처음 포인터+=1
6. sum이 찾는 값보다 크면 끝포인터-=1
7. 처음 포인터와 끝 포인터가 같아지면(만나면) break
8. 반복

위 조건으로 for문 2중첩 O(N^2)의 시간복잡도를 O(N)으로 줄일 수 있다.

Two Pointer는 자주 쓰이는 기법이니 문제를 풀며 감을 익히도록 하자.

---

✔️ 정답 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> number;
int result = 0;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, x, temp;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		number.push_back(temp);
	}
	cin >> x;

	int l = 0, r = number.size() - 1;
	sort(number.begin(), number.end());

	while (1) {
		if (l == r)
			break;
		int sum = number[l] + number[r];
		if (sum == x) {
			result++;
			r--;
		}
		else if (sum > x)
			r--;
		else
			l++;
	}
	cout << result;

	return 0;
}