temp = (int*)malloc(sizeof(int)*(right + 1));
이게 너무 많은 시간을 잡아먹을 것 같네요. 총 할당받는 공간이 O(n^2) 정도 되겠는데요. 미리 nums만한 크기의 임시배열을 통째로 만들어두고 계속 재사용하던지, 아니면 right - left + 1만큼의 공간만 할당받아서 알뜰하게 사용해야 합니다.
2751번 - 수 정렬하기 2
흐음..
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초 내에 들어오긴 어렵겠지요..
생각보다 빠르네요. 수가 작은 게 클 거 같군요.
TC에 따라서 달라질수도 있지 않을까 싶긴 하지만요. 예를 들어서 A배열과 B배열을 교대로 왔다갔다 하면서
합병을 해야 하는 경우라던지.. (근데 그 경우도 그렇게 크게 차이가 날 거 같지는 않네요.)
감사합니다 답변주신덕분에 잘 해결했어요! 정말 감사합니다
댓글을 작성하려면 로그인해야 합니다.
hwangsoon95 6년 전
merge sort 써서 풀었는데 자꾸 시간초과가 나네요... 어떻게 하면 해결할수 있을까요?