Programming Language/C++
vector upper_bound, lower_bound 사용 (C++)
Hugxy
2019. 9. 1. 12:19
배열에서, 특정 원소의 개수를 파악하는 것을 upper_bound 그리고 lower_bound를 활용해서 할 수 있다.
1 2 3 4 5 6 7 8 9 10 | sort(x.begin(), x.end()); vector<ll>::iterator low, high; for (int i = 0; i < x.size(); i++) { if (mp.find(x[i]) == mp.end()) { low = lower_bound(x.begin(), x.end(), x[i]); high = upper_bound(x.begin(), x.end(), x[i]); mp.insert({ x[i], high - low }); } } | cs |
당연하게도 두 bound의 특징을 활용해서 특정 원소의 개수를 파악하기 위해서는 정렬이 필수적이다.
위 코드의 경우, low에는 처음으로 벡터의 원소가 x[i] 이상이 되는 원소의 iterator가 반환되고,
high에는 벡터의 원소중, 처음으로 x[i] 초과가 되는 원소의 iterator가 저장된다.
이때 high 혹은 low에서 x.begin()을 빼주면 몇번째 위치인지를 파악할 수 있는 것이고,
이 과정을 생략하고 high와 low의 차이를 구하면, 두 iterator의 위치 차이를 구할 수 있기 때문에, x[i]의 개수가 구해지는 것이다.