0207free   2년 전

힙정렬로 푸는데

채점중(2%)에서 계속 시간초과가 뜹니다.

힙정렬을 제가 제대로 구현한게 맞을까요?

맞다면 제 코드에서 어떤 점을 수정해야 할까요?\

감사합니다.

djm03178   2년 전

HeapBuild는 힙이 아닌 상태의 배열을 힙으로 만들어주기 위한 함수이기 때문에 모든 원소를 입력받은 뒤에 한 번만 호출하면 됩니다. 힙을 만드는 데에 O(NlogN) 시간이 걸리므로 N개 원소를 입력받을 때마다 호출하면 O(N^2logN) 시간이 걸리게 됩니다.

0207free   2년 전

정말 감사합니다!

buildheap을 한 번만 하면 그 뒤부터는

heap의 첫번째 요소를 한번만 heapify 해주면 계속해서 heap이 만들어지는군요!!

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