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가 있는 이유가 있었네요...
댓글을 작성하려면 로그인해야 합니다.
stlee 3년 전 4
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가 있는 이유가 있었네요...