글 읽기 - 힙정렬로 구현시 시간초과가 발생합니다. 도움부탁드리겠습니다.

shfshfdl 5년 전 1

힙정렬로 구현시 시간초과가 발생합니다. 도움부탁드리겠습니다.

break 조건등이 누락되어서 시간초과가 발생할 것 같은데

계속 파고봐도 보이지가 않네요 :(

도움부탁드리겟씁니다.

감사합니다.

#include "stdio.h"
#define MAXN 1000002
#define ROOT 1

int n;

int tree[MAXN] = { 0, };

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

inline int min(int a, int b) {
	return (tree[a] <= tree[b]) ? a : b;
}

int leaf = 0;
void input(int num) {
	int curr = ++leaf;
	tree[curr] = num;

	// 위의 값보다 내가 더 작을때까지 root쪽으로 당겨감
	while (1) {
		if (curr == ROOT) break;
		int next = curr / 2;
		if (tree[next] > tree[curr]) {
			swap(&tree[next], &tree[curr]);
		} else {
			break;
		}
		curr = next;
	}
}

int sort() {
	int curr = ROOT;
	int ret = tree[ROOT];
	tree[ROOT] = tree[leaf--];

	while (1) {
		if (curr * 2 > leaf) { // 자식 노드가 없는경우
			break;
		} else if (curr * 2 + 1 <= leaf) { // 자식노드가 2개인 경우
			int next;
			if (min(curr, next = min(curr * 2, curr * 2 + 1)) != curr) {
				swap(&tree[next], &tree[curr]);
				curr = next;
			} else {
				break;
			}
		}
		else if (curr * 2 <= leaf) {
			int next;
			if (next = min(curr, curr * 2) != curr) {
				swap(&tree[next], &tree[curr]);
				curr = next;
			} else {
				break;
			}
		}
	}

	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);
		input(num);
	}

	for (int i = 0; i < n; i++) {
		printf("%d\n", sort());
	}


	return 0;
}

djm03178 5년 전 1

56번째 줄은 다음과 같은 의미입니다.

if (next = (min(curr, curr * 2) != curr)) {

shfshfdl 5년 전 0

아.. 연산 우선순위의 문제였군요.. :(
감사합니다. 저런실수를 줄이도록 좀더 노력해야겟네요

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

문제

문제

출처

ICPC

힙정렬로 구현시 시간초과가 발생합니다. 도움부탁드리겠습니다.

shfshfdl 5년 전 1

djm03178 5년 전 1

shfshfdl 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말