글 읽기 - 힙소트를 이용해 nlogn 구현시 시간초과가 납니다...도움 부탁드리겠습니다.

shfshfdl 4년 전 1

힙소트를 이용해 nlogn 구현시 시간초과가 납니다...

힙소트가 졸못되서 그럴거라는 생각은 드는데 정확히 어디가 잘못된지

캐치를 못하겠네요..

도움 부탁드리겠습니다.

#include "stdio.h"
#include <cstring>
using namespace std;

#define MN 20002
#define ML 52

int N;
char str[MN][ML] = { 0, };

int tree[MN] = { 0, };
int s = 0;
int sorted[MN] = { 0, };
int last = 1;

void swap(int * a, int * b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

// a가 b보다 더 작으면 true
bool cmp(int a, int b) {
	int lenA = strlen(str[tree[a]]);
	int lenB = strlen(str[tree[b]]);
	if (lenA == lenB) return strcmp(str[tree[a]], str[tree[b]]) < 0;
	return lenA < lenB;
}

void input(int index) {
	tree[last] = index;
	int curr = last;
	
	while (1) {
		if (curr == 1) {
			break;
		}

		if (cmp(curr, curr / 2)) {
			swap(&tree[curr], &tree[curr / 2]);
		} else {
			break;
		}

		curr /= 2;
	}

	last++;
}

int root = 1;

void printAns() {
	for (int i = 0; i<N; i++) {
		if (i>0)
			if (strcmp(str[sorted[i]], str[sorted[i - 1]]) == 0)
				continue;
		printf("%s\n", str[sorted[i]]);
	}
}

void sort() {
	for (int i = 0; i < N; i++) {
		//printTree();

		sorted[s++] = tree[root];
		int l = --last;
		tree[root] = tree[l];
		tree[l] = -1;

		int curr = root;
		while (1) {
			if (curr * 2 > l - 1) { // 자식 0개
				break;
			} else if ((curr * 2 + 1) < l) { // 자식 2개
				if (cmp(curr * 2, curr * 2 + 1)) {
					if (cmp(curr * 2, curr)) {
						swap(&tree[curr], &tree[curr * 2]);
						curr *= 2;
					}
				} else {
					if (cmp(curr * 2 + 1, curr)) {
						swap(&tree[curr], &tree[curr * 2 + 1]);
						curr *= 2;
						curr += 1;
					}
				}
			} else if ((curr * 2) < l) { // 자식 1개
				if (!cmp(curr, curr * 2)) {
					swap(&tree[curr], &tree[curr * 2]);
					curr *= 2;
				} else {
					break;
				}
			}
		}
	}
}

int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%s", str[i]);
		input(i);
	}
	sort();

	printAns();

	return 0;
}