백준 2470번 두 용액

1. 이분탐색

수들을 정렬한 array를 만들고 array에서 -x와 가장 가까운 array[mid]를 이진탐색을 통해 찾되
array[mid]가 가장 가까운 수가 아닐 수 있으므로 array[mid + 1], array[mid - 1]도 후보로 두었다.

내 코드

#include <stdio.h>
#include <stdlib.h>

int compare(int* x, int* y)
{
	if (*x < *y) return -1;
	else if (*x > *y) return 1;
	else return 0;
}

int array[100000];//특성값 저장
int brray[100000];//특성값 합 저장, 가장 0에 가까운 특성값을 min에 저장, 이와 비교할 것
//같으면 바로 array[i] 와 특성값 합 - array[i]를 순서대로 출력
int crray[100000];//절댓값 저장

int main()
{
	int i, N;
	int search, min = 2000000001;//min은 가장 작은 절댓값
	int left, right, mid;
	int x, y, z, k;

	scanf("%d", &N);
	
	for (i = 0; i < N; i++)
	{
		scanf("%d", &array[i]);
	}

	qsort(array, N, sizeof(int), compare);

	for (i = 0; i < N; i++)
	{
		left = 0;
		right = N - 1;
		search = -1 * array[i];
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (array[mid] < search) left = mid + 1;
			else if (array[mid] > search) right = mid - 1;
			else break;
		}
		x = array[mid - 1] + array[i];
		if (array[i] == array[mid - 1] || mid - 1 < 0) x = 2000000001;
		y = array[mid] + array[i];
		if (array[i] == array[mid]) y = 2000000001;
		z = array[mid + 1] + array[i];
		if (array[i] == array[mid + 1] || mid + 1 >= N) z = 2000000001;

		x = x > 0 ? x : (-1 * x);
		y = y > 0 ? y : (-1 * y);
		z = z > 0 ? z : (-1 * z);


		if (x < y)
		{
			if (x < z) brray[i] = array[mid - 1] + array[i];
			else brray[i] = array[mid + 1] + array[i];
		}

		else
		{
			if (y < z) brray[i] = array[mid] + array[i];
			else brray[i] = array[mid + 1] + array[i];
		}

		crray[i] = brray[i] > 0 ? brray[i] : (-1) * brray[i];
		min = min < crray[i] ? min : crray[i];	
	}

	for (i = 0; i < N; i++)
	{
		if (crray[i] == min)
		{
			printf("%d %d", array[i], brray[i] - array[i]);
			break;
		}
	}
	return 0;
}

다른 알고리즘(투 포인터)

left = 0, right = N- 1을 가리키고
두 합이 음수이면 left를 증가, 양수이면 right를 증가,
가장 절댓값이 작은 수를 min에서 저장하고 min_left_index, min_right_index를 저장한다.

left기준, 두 합이 음수이면 right를 감소시키는 것은 검사하는 의미가 없으므로 left가 다음 인덱스로 넘어가는게 맞고,
두 합이 양수이면 다른 후보도 검사해봐야하므로 right를 증가시키는게 맞다.

right기준, 두 합이 음수이면 다른 후보도 검사해보는게 맞으므로 left를 증가시키는게 맞고
두 합이 양수이면 left를 증가시켜 합을 크게해도 0에 가까워지지 못하므로 다음 후보를 검사하는 것이 맞다.

right기준으로 잠시 생각해서 right가 작아졌는데도 두 합이 양수이면? 그래도 left는 다시 작아질 필요가 없다

ex. -30, -13 , -10, 8, 15 , 25

이 경우를 보자 25에서 -30, - 13과의 합을 검사 후 15로 넘어왔다. 이 때 15와 -30의 합도 검사해봐야 하는 것아니냐 할 수 있지만
-30은 이미 25와의 합이 음수임에서 가장 최적의 경우를 검사하였으므로 left가 돌아갈 이유는 전혀 없다.