백준 11663번: 선분 위의 점 (C++)

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

11663번: 선분 위의 점

 

풀이

문제가 짧아서 쉽게 접근했다가 틀렸습니다 폭탄 맞았던 이분 탐색 문제.

 

선분의 시작점과 끝점 각각 이분 탐색을 돌려주어야해서 함수로 만들어주었다.

그리고 점의 좌표를 입력받고 추가로 가장 끝 값을 더 넣어줘서 백터의 오버플로우를 방지했다.

 

예제의 1  3  10  20  30 값을 넣는다 했을 때, (오버플로우 방지용 1987654321)

2와 60이 들어온다면, 0 ~ 60 까지 5개, 0 ~ 2 까지 1개, 2 ~ 60 까지는 총 4개가 포함되어 있다.

그러나 시작점이나 끝점이 좌표값과 같을 때 문제가 발생한다.

 

위와 같은 경우는 실제로는 4개가 포함되어 있지만 0 ~ 30 에서 0 ~ 3을 뺀다면 3개밖에 계산되지 않는다.

왜냐하면 3 에 해당하는 좌표가 추가로 빠져서 실제 값보다 -1 작은 값으로 나타난다.

 

이를 한 함수로 구현하기 위해서 시작점과 끝 점을 구분할 수 있는 int start를 binary_search의 인자로 넣어주었고

시작점과 좌표값이 같을 때를 예외로 처리해주었다.

if (v[mid] == x && start == 1) return ret - 1;

 

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> v;
int x1, x2;

int binary_search(int x, int start) {
	int left = 0, right = v.size() - 1, ret = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (v[mid] <= x) {
			ret = mid + 1;
			if (v[mid] == x && start == 1) return ret - 1;
			left = mid + 1;
		}
		else right = mid - 1; 
	}
	return ret;
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	v.push_back(1987654321);

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

	for (int i = 0; i < M; i++) {
		cin >> x1 >> x2;
		cout << binary_search(x2, 0) - binary_search(x1, 1) << '\n';
	}
}