두 용액 (feat. 백준, 2470번)

두 용액
https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int N;
long long arr[100000];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
	for (register int n = 0; n < N; ++n)
		cin >> arr[n];
	sort(arr, arr + N);
	register int s = 0, e = N - 1, as, ae;
	register long long minnn = 2000000001;
	while (1) {
		if (s >= e)
			break;
		if (arr[s] + arr[e] == 0) {
			as = s, ae = e;
			break;
		}
		else {
			if (arr[s] + arr[e] < 0) {
				if (abs(arr[s] + arr[e]) < minnn)
					minnn = abs(arr[s] + arr[e]), as = s, ae = e;
				++s;
			}
			else {
				if (abs(arr[s] + arr[e]) < minnn)
					minnn = abs(arr[s] + arr[e]), as = s, ae = e;
				--e;
			}
		}
	}
	cout << arr[as] << " " << arr[ae];
	return 0;
}
// *&)*@*

1. 투포인터 알고리즘은 두개의 인덱스 (start, end 또는 low, high) 로 진행됩니다.
2. 앞과 뒤의 인덱스가 서로 반전될때까지 비교하는 방식입니다.