kanghun8871   2년 전

어제부터 열심히 코드짜서 틀리고 또 짜고 했는데도

마지막엔 시간초과가 나네요,,,

merge sort했는데도 이래요,,ㅠ

도와주시면 감사하겠습니다

djm03178   2년 전

메모리 할당은 상수 시간이 아니라, 할당하는 크기에 비례합니다. O(size)번의 merge 함수의 호출에 O(size)씩 메모리를 할당하고 해제하니, 총 시간은 O(size^2)가 됩니다.

꼭 필요한 만큼씩만 할당하고 해제하든지, merge를 위한 메모리를 미리 할당해두고 해제 없이 끝까지 사용하세요.

djm03178   2년 전

보니까 할당 뿐만 아니라 전체를 옮겼다가 다시 되돌리고 있으니 전체적으로 다 O(size^2)이네요.

kanghun8871   2년 전

감사합니다!!

시간초과문제는 해결했는데

이제는 답이 틀렸다고 나오네요,,,ㅠ

제가 생각치 못한 반례가 있나봐요

kanghun8871   2년 전

반례가 더 있을까요,,

djm03178   2년 전

51을 모두 52로 바꾸면 맞습니다. 50글자가 한 줄에 들어오면 50 + 개행 문자 + 널 문자까지 총 52칸이 필요합니다.

djm03178   2년 전

그래서 이런 문제에서는 개인적으로 fgets는 비추합니다. scanf("%s")가 낫습니다.

kanghun8871   2년 전

네 방금 문제 맞았습니다!!

조언 감사합니다!!

행복한 하루되세요

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