개인 자료란 (JE)

  서버 커뮤니티

Profile 배고픈상어-효묘 대표칭호 없음
Profile

질문하기 C

c언어 힙정렬 질문..

2020.02.17 조회 수 160 추천 수 0
이해도 기타 

백준 2751번. 시간복잡도가 O(n*log(n)) 정렬을 쓰랍니다. 힙정렬이 nlogn이라길래 알고리즘 구현해봤는데  시간 초과가 뜨네요.. 뭔가 쓸때없는 연산을 했다는건데 어디가 잘못될 걸까요?

#define _CRT_SECURE_NO_WARNINGS#include <iostream>using namespace std;#define FOR(i, n) for(int i = 0 ; i < n ; i++)void heapSort(int *arr, int lo, int hi);void hSort(int *arr, int root, int hi);void downHeap(int *arr, int hi, int root, int c);int partialSort(int *arr, int root, int hi);int main() {	srand((unsigned)time(NULL));	int n;	int *arr=NULL;	cin >> n;	arr = (int*)calloc(n, sizeof(*arr));	FOR(i, n) {		int k;		cin >> k;		arr[i] = k;	}cout << endl;	heapSort(arr, 0, n - 1);	FOR(i, n) {		cout << arr[i] << "\n";	}	return 0;}void heapSort(int *arr, int lo, int hi) {	int last = hi;	while (last > 0) {		hSort(arr, lo, last);		int tmp = arr[lo];		arr[lo] = arr[last];		arr[last] = tmp;		--last;	}}void hSort(int *arr, int root, int hi) {	int r = root;	int c1 = r * 2 + 1;	int c2 = r * 2 + 2;	//maxHeap 한 번만	//downHeap	if (r <= hi && c1 <= hi) {		hSort(arr, c1, hi);		hSort(arr, c2, hi);		int c = partialSort(arr, r, hi);		//왼쪽 자식과 바꾸면 c = 1, 우측 자식과 바꾸면 c = 2, outOfIndexRange이거나 안 바꾸면 c = 0		//c값에 따라서 donwHeap을 하는 것임		downHeap(arr, hi, r, c);	}}void downHeap(int *arr, int hi, int root, int c) {	if (c == 0)return;	int r = root;	int c1 = r * 2 + 1;	int c2 = r * 2 + 2;	if (c == 1 && c1<=hi) {		int k = partialSort(arr, c1, hi);		downHeap(arr, hi, c1, k);	}	else if(c==2 && c2<=hi){		int k = partialSort(arr, c2, hi);		downHeap(arr, hi, c2, k);	}}int partialSort(int *arr, int root, int hi) {	int r = root;	int c1 = r * 2 + 1;	int c2 = r * 2 + 2;	//	if (c2 > hi) {		if (c1 > hi) {			return 0;		}else {			if (arr[c1] > arr[r]) {				int tmp = arr[r];				arr[r] = arr[c1];				arr[c1] = tmp;				return 1;			}			else {				return 0;			}		}	}	if (arr[c1] > arr[c2]) {		if (arr[c1] > arr[r]) {			int tmp = arr[r];			arr[r] = arr[c1];			arr[c1] = tmp;			return 1;		}	}else if (arr[c2] > arr[r]) {		int tmp = arr[r];		arr[r] = arr[c2];		arr[c2] = tmp;		return 2;	}	return 0;}



2개의 댓글

camelCase
2020.02.17

저라면 저거 코드 한줄한줄 읽기보다는 간단한 테스트 로직 짜서 IDE로 돌려볼것 같네요.

본인 컴퓨터에서 테스트 한번 해보세요

디버깅은 바텀업이아니라 탑다운으로 하는게 편합니다

@camelCase

작동은 합니다! 다만 시간초과가 걸릴뿐..ㅠ

뉴스 및 창작물
/files/thumbnails/520/751/003/262x150.crop.jpg?20240328020349

레드스톤

마인크래프트 노트블록으로 만든 『 Bling‐Bang‐Bang‐Born 』 1

Sonttukk

2024-03-23

1

/files/thumbnails/467/742/003/262x150.crop.jpg?20240311163123

레드스톤

[노트블럭커버] MILGRAM -ミルグラム(밀그램)- / 아마네 「숙청 행진」 제 2심 2

리비온

2024-03-11

0

/files/thumbnails/846/741/003/262x150.crop.jpg?20240310221214

레드스톤

워든 vs 라마 200마리 1

GlassesFilm

2024-03-10

0

/files/thumbnails/542/739/003/262x150.crop.jpg?20240309070457

레드스톤

[고인의 명복을 빕니다][노트블럭]드래곤볼 GT 오프닝 - 점점 마음이 끌려

리비온

2024-03-09

0

/files/thumbnails/326/738/003/262x150.crop.jpg?20240328020414

레드스톤

마인크래프트 노트블록으로 만든 『 Build Our Machine 』

Sonttukk

2024-03-07

0