blackout   1년 전

더 빠른 풀이가 있는 건 알지만 O(NlgN)도 될텐데 제출해보니 시간 초과가 납니다

set이 특별히 무거운 자료구조는 아닐텐데 왜 이런 걸까요?

zenith82114   1년 전

이 문제는 N <= 100만에 제한이 1초로 O(N) 풀이를 써도 시간이 아주 여유롭지는 않습니다. 더구나 set은 STL 컨테이너 중에서 손꼽을 정도로 느린 축에 속합니다.

azruine   1년 전

O(N) 풀이가 200ms 정도인데, N 이 10^6 이라서 log2 N 이 대충 20배정도 됩니다. 이거 log 붙이려면 상수 커팅해야할거에요.

수정 : N log N 으로 풀어보니까 580ms 정도 나오네요. set이 윗 분 말씀대로 무거워서 안 뚫린다고 봐야할거 같습니다.

blackout   1년 전

set이 생각보다 무거운 자료구조였군요...

감사합니다!

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