백준 2751) 수 정렬하기 2

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

-> 위 문제에서는 stl을 쓰기를 권장하고 있지만... 자료구조도 다시 기억 해볼겸 힙 정렬로 짜보기로 했다.

하지만 top-down 방식으로 힙을 구성했더니 계속 타임리밋에 걸렸다..  아무래도 bottom-up 방식으로 정렬하는게 훨 씬 빠른 것 같아서 그런 식으로 짜야하는 것 같다.

 

https://blog.weirdx.io/post/3122

C++ 힙 정렬 (Heap Sort), Bottom-up 과 Top-down 구현 - 이상한모임

=> bottom-up construction은 O(n)+O(nlogn) 시간이 걸리는 반면, top-down 방식은 O(nlogn)+O(nlogn)시간이 

걸리기 때문에 훨씬 오래 걸리는 것 같다.

 

#include <cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAX = 1000000;
int n, heap[MAX];

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

void max_heap(int cur, int size) {
	while (cur < size) {
		int left = cur * 2 + 1;
		int right = cur * 2 + 2;
		if (left < size || right < size) {
			int tmp = cur;
			if (left < size) {
				if (heap[left] > heap[tmp])tmp = left;
			}
			if (right < size) {
				if (heap[right] > heap[tmp])tmp = right;
			}
			if (tmp == cur)break;
			swap(heap[cur], heap[tmp]);
			cur = tmp;
		}
		else break;
	}
	return;
}

void heapify() {
	for (int i = (n - 1) / 2; i >= 0; i--) {
		max_heap(i, n);
	}
}

int main() {
	memset(heap, 0, sizeof(heap));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &heap[i]);
	}
	heapify();
	for (int i = n - 1; i > 0; i--) {
		swap(heap[0],heap[i]);
		max_heap(0, i);
	}

	for (int i = 0; i < n; i++) {
		printf("%d", &heap[i]);
	}
	return 0;
}

+) 일단 cin/cout을 썼더니 자꾸 타임리밋이 걸리는 문제가 발생했다. 다른 분 코드를 보고 참고했더니 printf와 scanf로 속도를 훨씬 빠르게 한 것을 볼수 있었다. 최대한 입출력 함수는 printf/scanf를 써야겠다.