[백준] 14746번 Closest Pair C++ 문제풀이

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

14746번: Closest Pair

문제 풀이

문제 조건에서 n과 m이 최대 500000이기 때문에.O(n^2)의 시간복잡도를 갖는 알고리즘은 시간초과가 날 것이라고 생각했다.

이 문제는 결국 y좌표는 고정이기 때문에, x좌표가 가까운 점들 간의 거리를 구하는 게 목표인 문제이다. 

vector 하나에 2개의 p_x, q_x점을 넣어두고,,정렬한 뒤 앞, 뒤의 점이 만약 다른 좌표인 경우만 거리를 구해 경우를 세줬다.

이려면 O(n+m)이기 때문에 시간 초과에 걸리지 않고 문제를 해결할 수 있었다.

소스 코드

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

vector<pair<int,int>> point;

int main() {
	int n, m;
	cin >> n >> m;
	int y1, y2;
	cin >> y1 >> y2;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		point.push_back(make_pair(a,0));
	}
	for (int j = 0; j < m; j++) {
		int b;
		cin >> b;
		point.push_back(make_pair(b, 1));
	}
	sort(point.begin(), point.end());

	int min_value = 4 * 100000000;
	int cnt = 1;
	for (int i = 0; i < n + m - 1; i++) {
		if (point[i].second != point[i+1].second) {
			int dis = abs(point[i].first - point[i + 1].first);
			if (dis < min_value) {
				min_value = dis;
				cnt = 1;
			}
			else if (dis == min_value) {
				cnt += 1;
			}
		}
	}
	cout << min_value + abs(y1 - y2) << " " << cnt << '\n';
}