[백준/C++] 두 용액

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 두 용액의 합이 0에 가까운 경우를 구하는 문제다.

만약 0에 가장 가까운 경우가 여러개라면 아무 경우나 출력하면 된다.

 

단순히 2중 for문으로 문제를 풀면 O(n^2)의 시간복잡도가 걸린다.

 

하지만 이 문제는 정렬을 하면 O(nLogn)의 시간복잡도로 문제를 풀 수 있게 된다.

 

오름차순으로 정렬을 한 다음 양쪽 끝에서 탐색을 시작한다.

 

이후 양쪽의 용액의 합이 0보다 작다면 왼쪽에 있는 용액을 오른쪽으로 이동시키면 된다.

 

정렬 돼 있기 때문에 왼쪽의 용액과 오른쪽 끝에 있는 용액을 더한 값이 0보다 작다면, 현재 왼쪽에 있는 용액과 더해서 0에 가까워 지는 용액은 없기 때문에 왼쪽의 용액은 탐색을 종료하는 것이다.

 

마찬가지로 현재 용액의 합이 0보다 크다면 현재 오른쪽에 있는 용액보다 오른쪽에 있는 용액들은 고려할 필요가 없다.

 

이렇게 비교를 하는 알고리즘을 투 포인터 알고리즘이라고 하며, O(n)으로 탐색을 끝낼 수 있다.

 

탐색을 하면서 왼쪽에 있는 용액이 오른쪽에 있는 용액의 Index와 같거나 커지면 탐색을 종료하면 된다.

(왼쪽에 있는 용액이 오른쪽의 용액보다 커지는 경우는 이미 이전에 탐색을 한 경우가 되기 때문에 탐색할 필요가 없다)

 

​

[아이디어 정리]

1. 숫자들을 오름차순으로 정렬한다.
2. 정렬한 숫자의 양끝에서 탐색을 시작하고 두 수의 합이 0보다 작다면 왼쪽의 Index를 늘린다.
3. 두 수의 합이 0보다 크다면 오른쪽의 Index를 줄인다.
4. 만약 두 수의 합이 0이면 두 수를 저장한 다음 탐색을 종료한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
	int n;
	int minV = 2000000000;
	int retSt=0, retEd=0;
	cin >> n;
	vector<int>v(n);
	
	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end(), [](int a, int b) {return a < b; });

	int st = 0, ed = n - 1;

	while(st<ed)
	{
		int nowNum = v[ed] + v[st];
		if (abs(nowNum)<minV)
		{
			minV = abs(nowNum);
			retSt = v[st], retEd = v[ed];
		}
		if (nowNum>0)
			ed--;
		else if (nowNum<0)
			st++;
		else
			break;
	}
	cout << retSt << " " << retEd;
	return 0;
}

 

---

왜 투포인터 알고리즘으로 문제를 풀어야 하는지 이해한다면 쉽게 풀 수 있는 문제였다.

 

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