17298번 - 오큰수
더 빠른 풀이가 있는 건 알지만 O(NlgN)도 될텐데 제출해보니 시간 초과가 납니다
set이 특별히 무거운 자료구조는 아닐텐데 왜 이런 걸까요?
O(N) 풀이가 200ms 정도인데, N 이 10^6 이라서 log2 N 이 대충 20배정도 됩니다. 이거 log 붙이려면 상수 커팅해야할거에요.
수정 : N log N 으로 풀어보니까 580ms 정도 나오네요. set이 윗 분 말씀대로 무거워서 안 뚫린다고 봐야할거 같습니다.
set이 생각보다 무거운 자료구조였군요...
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
blackout 1년 전
더 빠른 풀이가 있는 건 알지만 O(NlgN)도 될텐데 제출해보니 시간 초과가 납니다
set이 특별히 무거운 자료구조는 아닐텐데 왜 이런 걸까요?