백준 - 2467번 : 용액 (C++)

풀이 방법 : 투 포인터

데이터가 오름차순으로 정렬된 상태로 입력되므로 양 끝을 처음 기준으로 삼아 탐색한다.

만약 양 끝의 용액의 합이 양수일 경우 0에 더 가까워지기 위해서는 더 작아져야 하므로 큰 쪽의 수를 줄여준다. 즉, 오른쪽 포인터를 왼쪽으로 옮겨준다. 마찬가지로 음수일 경우 0에 더 가까워지기 위해서는 왼쪽 포인터를 오른쪽으로 옮겨줘야한다.

만약 합이 0일 경우 그 경우가 가장 가까운 경우라는 뜻이므로 탐색을 중단하고 바로 해당 경우를 출력해주면 된다.

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

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

	int N;
	cin >> N;

	vector<long long> vecLiquid(N);

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

	int Left = 0;
	int Right = N - 1;

	long long Max = LLONG_MIN;
	long long Min = LLONG_MAX;

	long long PrevSum = LLONG_MAX;

	while (Left < Right)
	{
		long long Sum = vecLiquid[Left] + vecLiquid[Right];

		if (abs(Sum) < abs(PrevSum))
		{
			Max = vecLiquid[Right];
			Min = vecLiquid[Left];
			PrevSum = Sum;
		}

		if (Sum < 0)
		{
			++Left;
		}

		else if (Sum > 0)
		{
			--Right;
		}

		else
		{
			break;
		}
	}

	cout << Min << ' ' << Max;
}