[백준,c++] 11663번 - 선분 위의 점

문제

11663번: 선분 위의 점

 

코드

#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> v;
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        v.push_back(inp);
    }
    sort(v.begin(), v.end());
    for(int i=0; i<M; i++){
        int a, b; cin>>a>>b;
        int first = lower_bound(v.begin(), v.end(), a) - v.begin();
        int second = upper_bound(v.begin(), v.end(), b) - v.begin();
        cout<<second - first<<'\n';
    }
    
}

 

풀이

그냥 a이상 b이하인 값의 개수가 몇 개인지 출력하면 됩니다.

upper_bound를 사용해서 b보다 큰 값의 첫 인덱스를 찾고

lower_bound를 사용해서 a보다 같거나 큰 첫 인덱스를 찾습니다.

따라서 upper_bound_index - lower_bound_index를 하면 a이상 b이하인 값의 갯수를 알 수 있습니다.