[Algorithm] Distance in set

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

 

해당 문제를 해결하는 과정에서 다음과 같은 생각을 했다. 

std::set은 정렬된 컨테이너로 특정 숫자의 upper bound에 해당하는 인덱스를 알기 어렵구나. 

 

 

set.upper_bound({idx, val}) - set.begin()

 

이 연산이 지원되지 않았다. 

 

대신, distance 연산이 있었다.

 

distance(set.upper_bound({idx, val}), set.begin());

 

으로 활용될 수 있었다. 다만 이는 시간복잡도는 o(n)이다. 그렇기에 상수의 시간복잡도가 필요한 경우, 인덱스 연산이 가능한 vector 의 사용을 고려해야 한다.