hwangsoon95   6년 전

merge sort 써서 풀었는데 자꾸 시간초과가 나네요... 어떻게 하면 해결할수 있을까요?

djm03178   6년 전

temp = (int*)malloc(sizeof(int)*(right + 1));

이게 너무 많은 시간을 잡아먹을 것 같네요. 총 할당받는 공간이 O(n^2) 정도 되겠는데요. 미리 nums만한 크기의 임시배열을 통째로 만들어두고 계속 재사용하던지, 아니면 right - left + 1만큼의 공간만 할당받아서 알뜰하게 사용해야 합니다.

chogahui05   6년 전

흐음..

temp = (int*)malloc(sizeof(int)*(right + 1));

이렇게 많이 할당할 필요가 있을까요? malloc을 쓴다면..

사실 그렇게 많이 할당 안 해도 됩니다. 어짜피 left부터 right까지만 보면 되는 것이니


(int *)malloc(sizeof(int)*(right-left+1));

이 정도만 하면 됩니다. 그러면 O(nlogn)만치의 공간을 할당받고 해제하고 그러겠네요..


그런데. 이게 n=100만이다 보니

f(n)=nlogn에서 f(100만) = 대충 2000만 즈음 됩니다. 그런데 앞에 k가 문제죠..


k는 merge에서 발생하는데요.

left 배열과 right 배열을 비교하고.. (1)

더 작은 경우에 합병할 배열에 접근해서 (2)

집어넣습니다. (3)


대충 k가 3 정도 될 거 같은데요? 분기문이면 조금 더 걸릴 거고..

당연한 이야기겠지만 (1)과 (2)도 배열의 크기가 커져버리는 경우에는 만만치 않은 작업이 됩니다.

심지어 malloc까지 하셨잖아요. free도 하셨고..


이 비용 결코 무시 못해요.. O(nlogn)짜리로도 충분히 통과는 가능하겠지만

솔직히 조금 빡셉니다. 100만개의 데이터를 입력받는 문제가 왕왕 있는데요.


O(nlogn)짜리로 풀릴만한 것이 시간 초과가 되는 경우가 많습니다.

안 그래도 입력에 많은 시간이 걸렸는데 앞에 상수까지 크다면 1초 내에 들어오긴 어렵겠지요..

djm03178   6년 전

제가 이 문제 정확히 right - left + 1씩 할당하고 해제하고를 반복한 병합 정렬로, 404MS에 통과했습니다. 물론 이보다 빠른 방법들이 많지만, 할당 크기만 조정해주면 1초가 빡셀 정도는 아닙니다.

chogahui05   6년 전

생각보다 빠르네요. 수가 작은 게 클 거 같군요.

TC에 따라서 달라질수도 있지 않을까 싶긴 하지만요. 예를 들어서 A배열과 B배열을 교대로 왔다갔다 하면서

합병을 해야 하는 경우라던지.. (근데 그 경우도 그렇게 크게 차이가 날 거 같지는 않네요.)

hwangsoon95   6년 전

감사합니다 답변주신덕분에 잘 해결했어요! 정말 감사합니다


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