[백준 C++] 2467 용액 - 투포인터

2467번: 용액

#include <iostream>
using namespace std;

int Solution[100000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> Solution[i];
	}

	int ResultSum = 2000000000;
	int ResultLeft = 0;
	int ResultRight = 0;

	int L = 0;
	int R = N - 1;
	while (L < R)
	{
		int Left = Solution[L];
		int Right = Solution[R];
		int Sum = Left + Right;

		if (abs(Sum) < abs(ResultSum))
		{
			ResultSum = Sum;
			ResultLeft = Left;
			ResultRight = Right;
		}

		if (Sum == 0)
		{
			break;
		}
		else if (Sum < 0)
		{
			++L;
		}
		else
		{
			--R;
		}
	}

	cout << ResultLeft << ' ' << ResultRight;
}

---

 

투 포인터를 이용해서 주어진 데이터를 O(N)으로 탐색하는 문제입니다.

 

용액의 특성값이 오름차순으로 정렬되어 있기 때문에

양쪽 끝에 인덱스 포인터를 두고 포인터를 이동시키면서 각 용액의 합을 비교하면 됩니다.

 

두 용액의 합이 0인 경우: 답 출력

두 용액의 합이 0보다 작은 경우: 왼쪽 포인터 오른쪽으로 1칸 이동

두 용액의 합이 0보다 큰 경우: 오른쪽 포인터 왼쪽으로 1칸 이동

 

양쪽 포인터가 같아질 때까지 위 동작을 반복합니다.