백준 - 두 용액 (2470) [C++]

이 문제는 투 포인터를 이용해서 풀었다.

 

예전에 이분 탐색으로 풀다가 계속 틀려서 때려쳤던 기억이 있다.

이번에는 투 포인터가 먼저 보여서 투 포인터로 풀었는데, 한번에 풀 수 있었다.

N <= 100,000 이므로 O(N log N)까지의 알고리즘이 시간 초과가 나지 않는다.
양 끝단에서 시작하는 투 포인터를 생각했다. 각 양쪽에서 서로를 향해 이동하는데, 각자의 다음 위치로 미리 이동한 후 더 절댓값이 작아지는 쪽으로 이동시키는 로직으로 알고리즘을 구성했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> input;
int N;

int absolute(int n) {
	return n >= 0 ? n : -n;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		input.push_back(tmp);
	}

	sort(input.begin(), input.end());

	int left = 0;
	int right = input.size() - 1;
	int answer = absolute(input[left] + input[right]);
	pair<int, int> result = { input[left], input[right] };
	
	while (left < right) {
		int presentSum = absolute(input[left] + input[right]);
		
		if (presentSum < answer) {
			answer = presentSum;
			result = { input[left], input[right] };
		}

		int nextLeft = input[left + 1];
		int nextRight = input[right - 1];
		
		if (absolute(nextLeft + input[right]) >= absolute(input[left] + nextRight)) {
			right--;
		} else {
			left++;
		}
	}

	cout << result.first << " " << result.second << '\n';

	return 0;
}