0805jw   1년 전

시간초과로 자꾸 틀리는데

시간초과 관련해서 조언을 얻고 싶습니다 !

skuru   1년 전

https://en.cppreference.com/w/...

임의 접근이 가능한 iterator가 아니라면 distance의 시간 복잡도가 $O(N)$이라고 합니다. 그래서 총 시간 복잡도가 $O(N^2\log N)$이 되어 시간 초과를 받는 것 같아요.

std::vector를 사용하시거나 std::map을 이용해서 각 값마다 인덱스를 저장하는 방식으로 하면 될 것 같아요.

not_strober   1년 전

https://en.cppreference.com/w/cpp/iterator/distance.html

링크 접근이 안 되는 것 같아서 링크를 남깁니다.

Complexity: Linear. However, if InputIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.

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