글 읽기 - (c++) 힙정렬 틀렸습니다...

jungby1 5년 전 0

비주얼 스튜디오에서는 아무리 다른 예제를 넣어봐도 잘 나오는 것 같고, 마이너스 값도 다 잘 정렬이 되는 거 같은데 한 4% 정도에서 틀렸다고 나오네요..

논리구조는 맞는거 같은데 사소한 에러가 나서 그런 거 같긴한데 그게 뭔지 잘 모르겠습니다... 고수분들 도와주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>

using namespace std;

void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

void shiftdown(int *arr, int a, int size) {
	
	int p = a, idx;
	int max = -1000001;

	if (max < arr[a]) {
		max = arr[a];
	}
	if ( a * 2 + 1 <= size && max < arr[a * 2 + 1]) {
		max = arr[a * 2 + 1];
		p = a * 2 + 1;
	}
	if (a * 2 + 2 <= size && max < arr[a * 2 + 2]) {
		max = arr[a * 2 + 2];
		p = a * 2 + 2;
	}
	swap(arr[a], arr[p]);
	
	if (p != a) {
		shiftdown(arr, p, size);
	}
}

void heapify(int *arr, int a, int size) {

	while (a >= 0) {
		shiftdown(arr, a, size);
		a--;
	}

}

int main() {

	int num; 
	cin >> num;
	int *arr = new int[num];
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
	}

	heapify(arr, num/2-1, num);

	int num1 = num-1;

	while (num1 >= 0) {

		swap(arr[0], arr[num1]);

		shiftdown(arr, 0, num1 - 1);
		num1--;
	}
	for (int i = 0; i < num; i++) {
		printf("%d\n", arr[i]);
	}

	delete[] arr;
	return 0;
}

bupjae 5년 전 1

입력 데이터에 없는 0이 갑자기 생기는 경우가 있습니다.

[입력]
2
-1
-2


[정답]
-2
-1


[오답]
-2
0

jungby1 5년 전 0

이상하네요 ... 제 비주얼 스투디오에서는 맞게 잘 나오는 듯 하는데.. 0이 나오는 이유도 딱히 없는 거 같고..ㅠㅠ

gaelim 5년 전 1

채점사이트 문제가 아니라, 소스의 문제 같습니다.

제일 먼저 shiftdown 함수 3번째 인자로 넘어가는 변수는 size 보다는 maxIdx 로 수정하는 것이 디버깅할 때 더 효과적일 것 같습니다.

size와 Index는 1차이가 나니까요. size : 1-base, Index : 0-base.

작성하신 heapify 함수, (통용적으론 BUILD HEAP이라 불리는 함수) 에서 3번째 인자를 size 자체로 넘기시는 걸 확인하였습니다.

1 차감하셔야합니다.

jungby1 5년 전 0

앗... 이런 실수를ㅋㅋㅋ 정말 감사합니다. 해결했네요

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

문제

문제

출처

ICPC

(c++) 힙정렬 틀렸습니다...

jungby1 5년 전 0

bupjae 5년 전 1

jungby1 5년 전 0

gaelim 5년 전 1

jungby1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말