백준(BOJ) 2470번 두 용액 **

일단 가장 단순하게 푼다면...

당연히 이러면 시간초과가 나겠죠?....
왜냐 시간복잡도가 n^2나오니까..
이 개념을 알고있는지를 물어보는 문제인 것 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#pragma warning(disable:4996)
using namespace std;

int s[1000005],mx,mi=1000000001,result[2];

int main()
{
	
	scanf("%d", &mx);
	for (int i = 0; i < mx; i++)
		scanf("%d", &s[i]);
	for (int i = 0; i < mx; i++)
		for (int k = i + 1; k < mx; k++)
			if (abs(s[i] + s[k]) < mi)
			{
				mi = abs(s[i] + s[k]);
				result[0] = s[i];
				result[1] = s[k];
			}
	if (result[0] < result[1])
		printf("%d %d", result[0], result[1]);
	else
		printf("%d %d", result[1], result[0]);
	return 0;
}

저런 방식으로 풀 수 없다는것을 알았다면 이제 해결 방법~
결국 절대값으로 정렬을 하면 시간복잡도 n으로 문제를 해결할 수 있습니다.
즉, 예시를 들면
-2 4 -99 -1 98 -> -1 -2 4 98 -99 로 정렬을 하면 쉽게 풀 수 있습니다.
(양 옆의 수만 확인 하면 되기 때문에)

** : 시간복잡도 개념을 이해하고 절대값으로 정렬하는 방법의 이해

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#pragma warning(disable:4996)
using namespace std;

int s[1000005],mx,mi=1000000001,result[2];

bool cmp(int a, int b){	return abs(a) > abs(b);}

int main()
{
	
	scanf("%d", &mx);
	for (int i = 0; i < mx; i++)
		scanf("%d", &s[i]);
	sort(s, s + mx, cmp);

	for (int i = 0; i < mx - 1; i++)
		if (abs(s[i] + s[i + 1]) < mi)
		{
			mi = abs(s[i] + s[i + 1]);
			result[0] = s[i];
			result[1] = s[i + 1];
		}
	if(result[0]<result[1])
		printf("%d %d", result[0], result[1]);
	else
		printf("%d %d", result[1], result[0]);
	return 0;
}