[BOJ 10816] 숫자찾기2 - lower_bound, upper_bound, equal_range, multiset

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

해당 문제는 주어진 N개(1<=N<=500000)의 숫자중에서 M개(1<=M<=500000)의 입력에 대해 그 숫자의 개수를 새는것이다. 물론 그냥 for문으로 반복하게되면 O(N^2)으로 시간초과에 걸리게 된다. 

이 때 활용해 볼 수 있는것이 바로 lower_bound , upper_bound , equal_range , multiset 정도가 될 것이다. 해당 문제를 통하여 저 4가지의 개념에 대해 짚고 넘어가는 기회가 되보도록 하자.

lower_bound는 정렬되어진 배열에서 해당숫자가 처음 나타나는 위치를 찾아준다. 비슷한 의미로 upper_bound는 해당 숫자보다 큰 처음 위치를 찾아준다. 해당 방법을 통하여 위의 문제를 풀어본다면 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n,m,number;
    scanf("%d",&n);
    
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    sort(a.begin(), a.end());
 
    scanf("%d",&m);
    
    for (int i=0; i<m; i++) {
        scanf("%d",&number);
        auto l = lower_bound(a.begin(), a.end(), number);
        auto r = upper_bound(a.begin(), a.end(), number);
        printf("%d ",r-l);
    }
    
    printf("\n");
    return 0;
}

위와 같이 풀어볼 수 있을 것이다.

그렇다면 이번에는 equal_range를 이용하여 풀어보도록 하겠다. equal_range는 lower_bound와 upper_bound를 동시에 구해준다.

for (int i=0; i<m; i++) {
    int number;
    scanf("%d",&number);
    auto p = equal_range(a.begin(), a.end(), number);
    printf("%d ",p.second - p.first);
    //second는 upper_bound값, first는 lower_bound값
}

멀티셋은 나중에 따로 포스팅하도록 하겠다.