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년 전 1
한 40% 대에서 시간초과가 나옵니다.
혹시이문제는 stl을 사용하면 시간오버가 나는건가요 아니면 제 코드에서 더 줄이면 가능할까요?
all 부분을 좀더 줄여보면 될거도 같은데.. 조언부탁드립니다.