kimsy96   6년 전

한 40% 대에서 시간초과가 나옵니다.

혹시이문제는 stl을 사용하면 시간오버가 나는건가요 아니면 제 코드에서 더 줄이면 가능할까요?

all 부분을 좀더 줄여보면 될거도 같은데.. 조언부탁드립니다.

chogahui05   6년 전

toggle 명령만 300만번 나온다면 시간초과 날 거 같은데요.

확실한 건 set 같은 경우, 삽입과 삭제가 O(1) 이 아니라 O(logn)에 비례해서 걸리는 건데요.

O(1)에 삽입, 삭제를 한다고 해도. 300만 x 20 = 6000만


만약에 O(logn)에 삽입, 삭제를 하면..

사실 rb 트리가 삽입, 삭제할 때. O(logn)이 걸리긴 하는데요. 균형도 맞춰줘야 하고..

회전도 시켜야 할 것이고.. 앞에 붙는 상수가 좀 커질 수도 있어요.


일단 단순히 앞에 붙는 상수가 없다고 가정하고

f(x) = ceil (logx / log2) 라고 가정하면..

f(1) + ... + f(20) = 0 + 1 + 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5 = 69

만약에 f(x) = floor(logx / log2)라면

f(1) + ... + f(20) = 0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 = 54


54에 300만을 곱하면 1.5억이 조금 넘어가네요. ㅎㅎ

kimsy96   6년 전

그렇군요... 직접 구현해야겠네요

감사합니다.

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