stlee   3년 전

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

2261번 : 가장 가까운 두 점


라인 스위핑을 적용해서 왼쪽에서부터 지나온 점들은 set에 저장하고 y의 범위를 한정해

후보 점을 찾아내기 위해 <algorithm>에 있는 upper_bound, lower_bound를 사용했는데

이상하게 계속 시간 초과가 나더군요.

근데 set 자료구조 자체에 있는 upper_bound, lower_bound를 이용하니 문제가 해결되었습니다...

https://stackoverflow.com/questions/31821951/c-difference-between-stdlower-bound-and-stdsetlower-bound

왜 그런가 이유를 찾아보니, set의 이터레이터가 양방향(bidirectional) 이터레이터라서,

랜덤 접근 이터레이터에 적합한 std::upper_bound, std::lower_bound가 매우 비효율적으로 작용하는듯 합니다.

set과 map에 따로 upper_bound, lower_bound가 있는 이유가 있었네요...

댓글을 작성하려면 로그인해야 합니다.