[백준] IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

테스트케이스를 보면, 중복된 숫자가 들어와서 multimap을 써서 전투력에 해당하는 여러 개의 칭호를 저장해야하나 순간 고민했다.

그런데 문제를 다시 한 번 잘 살펴보면, 어차피 첫 if문에 걸리기 때문에 2번째 중복되는 칭호는 신경 쓸 필요가 없어진다.

 

그리고 if문에 해당되는 값을 찾기 위해서는 set의 lower_bound 메소드를 써서 간편하게 칭호에 해당하는 값을 찾아낼 수 있다.

여기서 set의 lower_bound는 이진 탐색을 기반으로 하기 때문에 $O(logN)$이라는 시간 복잡도를 가진다.

std::lower_bound가 아니라 set의 lower_bound를 써야한다는 점에 주의를 기울여야 한다. std::lower_bound의 경우에는 랜덤 액세스 기반의 이터레이터이므로 최악의 경우 $O(N)$이라는 시간복잡도를 가지기 때문이다.