[11663] 선분 위의 점

11663번: 선분 위의 점

 

이분 탐색 문제다.

 

실버 3 문제라 쉽겠다 생각하고 아무 생각 없이 각 선분 마다 해당되는 점을 이분 탐색으로 찾았다가 시간초과가 났다. 당연한 얘기겠지만 제한 시간은 1초인데다 N과 M은 최대 100,000이라 N X M만 해도 1억을 훌쩍 넘긴다. (게다가 N X M X log2였다) 선분의 양 끝 값이 주어진 점보다 작은지 큰지 확인만 하면 되는 문제지만 주어진 점이 선분의 양 끝 값 A, B와 일일이 비교한다면 그런 N X M이 되어 제한 시간을 넘긴다. 따라서 A, B가 주어진 점들의 범위에 있는지 확인할 때 이분 탐색으로 시간을 단축하는 것이 관건이겠다. 나는 그 생각을 못 해서 다른 블로그 글을 참고했다.

 

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;

	cin >> n >> m;

	vector<int> dot; // 점
	vector<pair<int, int>> line; // 선분

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		dot.push_back(a);
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		line.push_back({a, b});
	}

	sort(dot.begin(), dot.end());

	// 각 선분의 끝 점보다 크거나 작은 점의 index를 가져와 둘의 차이를 구한다.
	for (int i = 0; i < m; i++) {
		int firstIndex = lower_bound(dot.begin(), dot.end(), line[i].first) - dot.begin();
		int lastIndex = upper_bound(dot.begin(), dot.end(), line[i].second) - dot.begin();

		cout << lastIndex - firstIndex << "\n";
	}

}

 

이분 탐색은 c++의 기본 함수인 lower_bound와 upper_bound를 사용했다. 이분 탐색으로 원하는 값 x보다 같거나 작은지, 같거나 큰지 확인하여 해당 index의 값을 return하는 함수다.

 

따라서 이 문제의 관건은

• 주어진 점들이 이분 탐색될 수 있도록 정렬하는 것.
• 정렬된 점들 중 A와 B보다 작거나 같거나 커지거나 같아질 때의 index를 구하는 것
• 구한 index를 가지고 선분 내부에 있는 점들의 개수를 구하면

답을 구할 수 있다.