[Codeup] 4701. 두 용액

1. 문제 링크

https://codeup.kr/problem.php?id=4701

코드업

 

 

2. 문제 풀이

모든 두 용액의 조합을 확인하면 O(N^2)이 걸린다.

N은 최대 100,000이므로, 전체 조합을 직접 확인하는 방식은 사용할 수 없다.

 

따라서 용액의 특성값을 오름차순으로 정렬한 뒤, 가장 작은 값과 가장 큰 값에 각각 포인터를 둔다.

두 값의 합이 0보다 작으면 합을 줄이기 위해 오른쪽 포인터를 왼쪽으로 이동한다.

 

각 단계마다 현재 합을 보고 정답을 갱신할지 판단한다.

 

3.  아이디어

1. 정렬된 배열에서는 왼쪽 포인터를 오른쪽으로 이동하면 선택되는 값이 커진다.
2.  오른쪽 포인터를 이동하면 선택되는 값이 작아진다.
3. 따라서, 현재 두 수의 합이 음수라면, 0에 가까워지게 하기 위해 합을 증가시켜야 하므로, 왼쪽 포인터를 오른쪽으로 1칸 이동한다.
4. 반대로 현재 두 수의 합이 양수라면, 0에 가까워지게 하기 위해 합을 감소시켜야 하므로, 오른쪽 포인터를 왼쪽으로 1칸 이동한다.
5. 이 과정을 통해서 0에 가장 가까운 두 수를 찾을 수 있다

 

4. 구현

※ C++ Source Code

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void)
{
	
	int n;
	int value[100005];
	int left, right;
	int sum = 0;
	int min = 2000000000;
	int ans1, ans2 = 0;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> value[i];
	}

	sort(value, value + n);
	
	left = 0;
	right = n - 1;

	while (left < right)
	{
		sum = value[left] + value[right];
		if (abs(sum - 0) < min)
		{
			min = abs(sum);
			ans1 = value[left];
			ans2 = value[right];
		}
		if (sum == 0) // 0이면 그대로 끝
		{
			break;
		}
		else if (sum > 0) // sum이 0보다 크면 오른쪽 값을 낮춰, sum을 줄여야한다.
		{
			right--;
		}
		else if (sum < 0) // sum이 0보다 작으면 왼쪽 값을 증가시켜 sum을 늘려야한다.
		{
			left++;
		}
	}
	cout << ans1 << " " << ans2;
}