hwjdghks2102   5달 전

set이 균형이진트리인 점을 이용하여 코드를 작성해보았는데 시간초과가 뜹니다.

의심되는 부분은 17번째 줄 인데, erase()가 느려서 시간초과가 발생한 걸까요? 

아니라면 코드의 어느 부분에서 시간을 많이 뺏기는지, 또는 알고리즘이 잘못 설계된 것인지 알고 싶습니다.

chogahui05   5달 전

(1) Cin과 Cout.

(2) 아마 알고리즘 구조상, arr에 들어가는 것은 N개가 전부일 겁니다.

그렇다면 N^2logN쯤 될 건데. N=1500이니까, 대략 225만 x 10 정도 될 겁니다. 그런데 set의 상수가 좀 크기 때문에

시간이 좀 빡빡하지 않나 싶어요. 아니 그렇다고 하기엔.. N이 작아서 걍 무난하게 통과될 거 같은데..

일단 Cin과 Cout만 고쳐보세요.

hwjdghks2102   5달 전

cin과 cout을 각각 scanf, printf로 바꾸니 해결되었습니다.

근데 여기서 궁금한 것이 있는데, 이전에는 cin과 cout의 버퍼가 묶여있어서 cin과 cout을 반복적으로 실행하면 느려지는 것으로 알고있었습니다.

하지만 cin만 반복적으로 실행해도 느려지는건 같은 이유에선가요?

hwjdghks2102   5달 전

버퍼 결합 때문에 시간초과가 나는 것같습니다. 아래 코드를 추가해도 해결이 되네요. 감사합니다.

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