kmc8724   4년 전

비쥬얼에서는 잘 정렬되는데, 여기서는 틀렸다고 나오네요.

어떤 경우가 틀렸는지 잘 모르겠네요.

한번 확인해주실수 있을까요??


수 정렬문제 3번 에서는 아애 시간초과가 뜨기도 하는군요.. ㄷㄷ

Heap sorting의 시간복잡도가 nlogn아니였나요..?

제가 알기로, sorting 문제에서 merge sort과 함께 최적 알고리즘으로 알고 있는데, 제가 코딩을 잘못한걸까요..


djm03178   4년 전

수 정렬하기 3은 nlogn에 안 풀어집니다. 문제 내에서 힌트를 찾아서, 비교하지 않는 정렬을 이용해서 O(n)에 해결해야 됩니다.

이 코드는 음수가 들어올 때 문제가 발생하네요.

3

-1 3 2

출력이 0 2 3으로 나옵니다.

kmc8724   4년 전

어... 잘 이해가 안되서 그런데, -1이 들어왔을때 0으로 바꿔서 출력해야한다는 의미인가요???

djm03178   4년 전

아니요, 원래 -1 2 3을 출력하는 게 맞는데, 이 프로그램이 0 2 3을 출력합니다.

https://doyak.s-ul.eu/p88ZDa6b

그대로 복붙해서 실행한 결과입니다.

kmc8724   4년 전

답변 너무감사합니다..

왜그런지 모르겠네요..ㅠㅠ 제 비쥬얼에서는 음수값도 잘 출력되는데.. 으어어ㅓ

djm03178   4년 전

컴퓨터마다 다를 것 같지 않은데요.

if (2 * root + 1 > size) 가 잘못된 조건이기 때문입니다.

-1 3 2를 차례대로 arr에 넣고 힙을 만들면, size == N == 3인 상태에서, arr[0]에 접근하게 됩니다.

여기서 fixHeap에 들어오면 이제 -1의 key를 아래로 내릴텐데, 우선 3이 arr[0]으로 올라가겠죠.

그 다음에 fixHeap(1, -1, 3) 이 호출됩니다. 그럼 여기가 리프 노드이므로 원래라면 if문에 걸려서 종료되어야 하죠. 그런데, 1 * 2 + 1은 3보다 크지 않습니다. else로 넘어가게 된다는 것입니다.

arr은 전부 처음에 0으로 초기화해놨기 때문에, 초기화되지 않은 원소들에 들어있는 값은 전부 0입니다. -1보다 큰 거죠. 즉 이 경우 arr[3]에 있던 0 값이 arr[1]로 올라가고, 한 번 더 재귀호출하게 됩니다.

결국 여기까지 끝낸 후의 배열의 상태는 3 0 2가 되는 거죠.

맞게 나오려면 조건이 2 * root + 1 >= size로 수정되어야 할 것으로 보입니다. size번째 원소는 사용할 수 없는 원소이므로, 2 * root + 1이 size이어도 root는 리프 노드입니다.

djm03178   4년 전

추가로

if ((size >= 2 * root + 2) && arr[2 * root + 1] < arr[2 * root + 2])

도 잘못된 것 같네요. size 가 2 * root + 2라는 건 오른쪽 자식은 없는 상태인 겁니다. 잘 생각해보세요. size == 4이면 arr[3]까지만 사용하게 한 게 현재 size의 의미입니다.

djm03178   4년 전

마지막으로, Heapsort 함수에서도 fixHeap(0, key, i); 로 호출해줘야 됩니다. size - 1번째 원소까지만 힙에 포함된다는 것이 size의 의미이기 때문입니다.

여기까지 수정한 뒤에 제출하니 AC를 받았습니다.

kmc8724   4년 전

소중한 답변 너무너무 감사합니다. 많이 배워갑니다!

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