(C++) 백준 3273 : 두 수의 합

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

3273번: 두 수의 합

 두 수의 합이 x가 되는 모든 순서쌍 조합을 찾는 문제입니다. 단순히 모든 두 순서쌍을 비교하려면 경우의 수가 n(n-1)/2 이므로 시간복잡도가 O(n^2)이 됩니다. 이 문제에서는 n이 최대 10^5 이므로 시간 초과가 되게 됩니다. 따라서 다른 방법을 사용해야 하는데 그 방법이 바로 투포인터 알고리즘 입니다. 투포인터 알고리즘은 리스트에 순차적으로 접근할 때 두 위치를 기록해가면서 처리하는 알고리즘입니다. 정렬되어있는 리스트에서 사용할 수 있는데 두 점에대해 특정 수보다 크거나 작은 경우에 따라 각각의 점을 이동하는 방식입니다. 두 점을 움직이지만 결국 각 점이 리스트를 한번만 순회하기 때문에 시간복잡도는 O(n)으로 나타 낼 수 있습니다. 따라서 정렬까지 포함하면 시간복잡도는 O(nlogn + n) ,즉 O(nlogn)이 됩니다. 투포인터 알고리즘을 사용한 부분입니다. s는 이미 정렬된 배열이고 x는 구해야하는 수, t는 합이 x인 순서쌍의 총

개수(구해야 하는 답)입니다. p1 과 p2가 각각의 점이고 p2는 n-1로 배열의 제일 마지막 부분부터 시작합니다. 

int p1=0, p2=n-1,sum,cnt1,cnt2,val;
	while (1)
	{
		sum = s[p1] + s[p2];
		if (sum < x) p1++;
		else if (sum > x) p2--;
		else
		{
			cnt1 = 1; cnt2 = 1;
			val = s[p1];
			while (p1<n && s[++p1] == val)
				cnt1++;
			val = s[p2];
			while (p2>=0 && s[--p2] == val)
				cnt2++;
			if (p1 > p2 && s[p1-1]==s[p2+1])
				t += (cnt1 * (cnt2 - 1)) / 2;
			else
				t += cnt1 * cnt2;
		}
		if (p1 >= p2)
			break;
	}

우선 현재의 두 점 p1, p2를 더하고 이 값이 x보다 작다면 p1 + p2가 더 커져야 하기 때문에 p1에 1을 더해줍니다. 반대로 두 점을 더한값이 x보다 크다면 p1 + p2는 더 작아져야 하므로 p2에 1을 빼줍니다. 만약 이 두 경우가 모두 아닌경우, sum 과 x가 같은 경우인데 단순히 서로 다른 p1, p2가 연속되지 않게 있는경우는 그냥 t++을 해주면 됩니다. 하지만 주의해야 하는 경우가 있습니다. 바로 같은 값이 연속으로 존재하는 경우입니다. 만약 같은값이 연속으로 나오는 경우를 예외처리 하지 않고 넘어간다면 합이 x인 순서쌍이 되는 많은 경우를 그냥 건너뛰게 될 것입니다. 예를 들어보겠습니다. 배열 s[10]={2,2,2,2,2,2,2,2,2,2} 이 있고 x=4인 경우입니다. 만약 값이 연속인 경우를 예외처리해주지 않는다면 p1 과 p2가 지나가면서 최대 9쌍밖에 찾아내지 못할 것입니다. 따라서 연속적으로 숫자가 나오는 경우는 예외처리를 해 주어야 합니다.

 

 이렇게 연속적으로 숫자가 나오는 경우에서도 또 두 경우로 나눌 수 있습니다. 위의 예시들였던 경우와 s[10]={1,1,1,1,1 ,4,4,4,4,4}  x=5 , 이러한 경우입니다. 전자의 경우는 모든 순서쌍을 구해야 하는데 p1<p2인 조건이 있었으므로 조합을통해 구해야 합니다. 하지만 후자의 경우에는 각각 1과 4가 나눠져 있으므로 항상 p1<p2입니다. 따라서 순서를 신경쓸필요없이 연속된 두 숫자의 갯수를 곱하면 됩니다. 

 

 이 문제는 문제자체가 어렵지는 않았는데 같은숫자가 연속적으로 나오는 경우에대해 어떻게 처리해야 할 것인가가 중요했던 문제였던것 같습니다. 투포인트 방식 말고도 푸는 방법이 있는데 그부분은 한번 고민해서 풀어보시면 좋을 것 같습니다.

전체 코드입니다.

#include<iostream>
#include<algorithm>

int s[100000];

int main() {
	int n,x,t=0;
	std::cin >> n;
	for (int i = 0; i < n; i++)
		std::cin >> s[i];
	std::sort(s,s+n);
	std::cin >> x;
	int p1=0, p2=n-1,sum,cnt1,cnt2,val;
	while (1)
	{
		sum = s[p1] + s[p2];
		if (sum < x) p1++;
		else if (sum > x) p2--;
		else
		{
			cnt1 = 1; cnt2 = 1;
			val = s[p1];
			while (p1<n && s[++p1] == val)
				cnt1++;
			val = s[p2];
			while (p2>=0 && s[--p2] == val)
				cnt2++;
			if (p1 > p2 && s[p1-1]==s[p2+1])
				t += (cnt1 * (cnt2 - 1)) / 2;
			else
				t += cnt1 * cnt2;
		}
		if (p1 >= p2)
			break;
	}
	std::cout << t;

}