[BOJ] 선분 위의 점 11663번 C++

 

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

 

접근 방식

 

C++의 STL을 사용하면 간단하게 풀 수 있다.

문제 자체는 끝점까지의 점의 개수 - 시작점 이전의 점의 개수를 구하면 쉽게 풀린다

이분 탐색으로 구현이 되어있는 lower_bound, upper_bound 함수를 사용하면 된다

lower_bound 함수는 주어진 범위에서 주어진 값보다 첫번재로 작은 원소의 위치를 반환하고 

upper_bound 함수는 주어진 범위에서 주어진 값보다 첫번째로 큰 원소의 위치를 반환한다

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N,M;
vector<int> v;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N>>M;
    for(int i=0; i<N; i++) {
        int x; cin>>x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());
    int s,e;
    while(M--) {
        
        cin>>s>>e;

        cout<<upper_bound(v.begin(), v.end(),e) - lower_bound(v.begin(),v.end(),s)<<'\n';

    }
}