10주차(이진탐색) - [C++]백준11663 선분 위의 점

22 May 2022 in Study on Algorithm

백준11663 선분 위의 점 링크

문제

예제 입력

---

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m;
vector<int> arr;

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        arr.push_back(h);
    }
    sort(arr.begin(), arr.end());

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        auto l = lower_bound(arr.begin(), arr.end(), a);
        auto r = upper_bound(arr.begin(), arr.end(), b);
        cout << r-l << '\n';
    }
}

설명

이 문제는 선분 위의 점이 주어지고 지정한 범위 안에 점의 갯수를 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 선분 위에 점을 입력 받고 해당 범위마다 몇개의 점이 있는 확인하기 위해서 키값 이상과 초과를 사용하여 결과를 출력합니다.

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬
-lower_bound(시작, 끝, 키) : key 값 이상인 위치
-upper_bound(시작, 끝, 키) : key 값 초과인 위치

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과