[BOJ10816] 숫자 카드 2

1. 문제

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

2. Note

std::lower_bound, std::upper_bound를 사용하는 문제

2.1. lower_bound(first, last, value)

value보다 크거나 같은 첫 번째 iterator 반환, 없을 시 last 반환

2.2. upper_bound(first, last, value)

value보다 큰 첫 번째 iterator 반환, 없을 시 last 반환

2.3. equal_range()

return std::make_pair(std::lower_bound(first, last, value),
                      std::upper_bound(first, last, value));

NOTE: 위 세 함수는 random access iterator가 아니면 선형 시간복잡도를 갖는다.

2.4. std::distance vs. operator-

Since only random access iterators provide + and - operators, the library provides two function templates advance and distance. These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.

https://stackoverflow.com/questions/1668088/advance-iterator-for-the-stdvector-stdadvance-vs-operator

3. Reference

• https://en.cppreference.com/w/cpp/algorithm/lower_bound
• https://en.cppreference.com/w/cpp/algorithm/upper_bound
• https://en.cppreference.com/w/cpp/algorithm/equal_range
• https://stackoverflow.com/questions/1668088/advance-iterator-for-the-stdvector-stdadvance-vs-operator