[백준-2467] 용액

전형적인 투포인터 문제이다.

10만의 입력값에 1초의 시간 제한을 보자마자 최소 O(NlogN)의 복잡도를 사용해야 한다는 것을 생각해야 한다. 또한 정렬이 되어있다는 조건을 본 후 이분탐색 또는 투포인터탐색을 떠올린 뒤 로직을 생각하면 된다.

이 문제의 경우 간단한 로직을 사용한다.

• lo, hi 를 양끝으로 잡은 뒤 값을 비교하며 투 포인터 탐색을 진행한다.
• 진행 시 계산한 값이 음수이면서 0에 가까운지 양수이면서 0에 가까운지 체크한다.
• 각 경우에 따라 lo를 증가시킬지 hi를 감소시킬지 정해주며 답을 찾아가면 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>

using namespace std;
int arr[100001];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	vector<int> ans(2);
	int minn = 2147483647, calc;
	
	for (int lo = 0, hi = n-1; lo < hi; ) {
		calc = arr[lo] + arr[hi];
		if (calc < 0) {
			if (abs(calc) <= minn) {
				minn = abs(calc);
				ans[0] = arr[lo];
				ans[1] = arr[hi];
				lo++;
			}
			else {
				lo++;
			}
		}
		else {
			if (abs(calc) <= minn) {
				minn = abs(calc);
				ans[0] = arr[lo];
				ans[1] = arr[hi];
				hi--;
			}
			else {
				hi--;
			}
		}
	}
	sort(ans.begin(), ans.end());
	printf("%d %d\n", ans[0], ans[1]);
	return 0;
}

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

2467번: 용액