BOJ 2467, 2470 : 두 용액

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/2467

www.acmicpc.net/problem/2470

 

 

BOJ 2467은 입력이 정렬이 되어서 들어오는 차이가 있다. 그 외 풀이는 BOJ 2470과 같다.

 

B형에서 어떤 조건을 만족하는 값을 찾으려면 대부분 정렬을 한 후, 이분 탐색으로 찾는다.

이분 탐색 외에도 답을 찾는 테크닉 중 하나가 투 포인터 알고리즘이다.

 

포인터(index) 2개를 이용하여 효율적으로 원하는 답을 찾는다.

---

두 용액 문제는 모든 배열의 값 2개 중 합이 0에 가까운 값 2개를 찾는다.

 

용액이 모두 양수라면 가장 작은 두 값이, 모두 음수라면 가장 큰 두 값이 답이 된다.

문제는 양수와 음수가 있는 경우이다.

이 경우는 가장 작은 값과 가장 큰 값을 더해보고 답을 찾아나가야 한다.

 

1) 용액을 모두 정렬한다. 그리고 가장 작은 수를 left pointer, 가장 큰 수를 right pointer로 정한다.

2) 먼저 작은 수(left pointer)와 큰 수(right pointer)를 먼저 더한다.

3) 더한 값이 기존 값보다 0에 더 가깝다면 갱신한다.

4) left pointer의 절댓값과 right pointer의 절댓값을 비교한다.

   4-1) 가장 작은 수의 절댓값이 더 크다면 left pointer를 올려 다음으로 작은 수를 가르킨다. 

   4-2) 가장 큰 수의 절댓값이 더 크다면 right poitner를 내려 다음으로 큰 수를 가르킨다.

5) 2)부터 반복한다.

 

4-1)의 경우에 left pointer의 절댓값이 더 크다면,

sum이 음수일 수 있으므로, sum을 더 커지게 하기 위해 left를 증가시킨다.

4-2)의 경우는 그 반대다.

sum이 양수일 수 있으므로, sum을 더 작아지게 하기 위해 right를 증가시킨다.

 

위의 방법대로라면 용액이 모두 양수인 경우 right pointer만 계속 감소하므로 결국 가장 작은 두 용액을 찾게 되고,

모두 음수인 경우는 left pointer만 커지므로 가장 큰 두 용액을 찾게 된다.

 

따라서 양수만 있는 경우, 음수만 있는 경우, 음수와 양수 모두 있는 경우 답을 찾을 수 있게 된다.

 

예제 -2 4 -99 -1 98의 경우 아래와 같은 과정으로 답을 찾게 된다. 

가장 처음 sum = -1이 갱신되고 그 이후는 갱신되지 않는다.

 

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

int N;

int a[100100];
int b[100100];

void merge(int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];
	
	for (i = start; i <= end;i++)
		a[i] = b[i - start];

}

void sort(int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1;

	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

int abs(int x)
{
	return (x > 0) ? x : -x;
}

int main(void)
{
	int lp, rp, lans, rans, tmp;

	scanf("%d", &N);

	for (int i = 0; i < N;i++) scanf("%d", &a[i]);

	sort(0, N - 1);

	lp = 0, rp = N - 1;
	lans = a[0], rans = a[N - 1];
	tmp = 0x7fff0000;

	while (lp < rp)
	{
		if (abs(a[lp] + a[rp]) < tmp) /* 현재 저장된 0보다 더 가까운 값이라면 */
		{
        	/* 두 용액을 저장하고, tmp를 갱신 */
			lans = a[lp];
			rans = a[rp];
			tmp = abs(a[lp] + a[rp]);
		}

		if (abs(a[lp]) > abs(a[rp])) lp++; /* left 절댓값이 더 큰 경우 left를 증가 */
		else rp--; /* 그렇지 않다면 right를 감소 */
	}

	printf("%d %d\n", lans, rans);

	return 0;
}