글 읽기 - 힙소트 구현시 시간초과가 아닌 틀렸습니다. 코드 점검 좀 부탁드리겠습니다.

shfshfdl 6년 전 1

n log n 으로 안될 수도 있다는 내용은 확인 했습니다.

그래서 시간초과를 기대하고 제출했는데 틀렸습니다가 발생하였는데

제 코드의 예외 상황을 찾질 못하겠네요

많은 도움 부탁드리겠습니다.

#include "stdio.h"
#define M 5000002
int arr[M] = { 0, };
int sorted[M] = { 0, };
int si = 1;

int lastIndex = 1;
void input(int n) {
	int curr = lastIndex++;

	arr[curr] = n;

	while (1) {
		if (curr <= 0) break;

		if (arr[curr] < arr[curr / 2]) {
			int temp = arr[curr / 2];
			arr[curr / 2] = arr[curr];
			arr[curr] = temp;
			curr /= 2;
		} else {
			break;
		}
	}
}

int root = 1;
void sort() {
	int curr = root;
	sorted[si++] = arr[curr];

	arr[curr] = arr[--lastIndex];

	while (1) {
		if (curr * 2 >= lastIndex) break;

		if (curr * 2 + 1 < lastIndex) {
			if (arr[curr * 2] >= arr[curr * 2 + 1]) {
				if (arr[curr] > arr[curr * 2 + 1]) {
					int temp = arr[curr * 2 + 1];
					arr[curr * 2 + 1] = arr[curr];
					arr[curr] = temp;

					curr *= 2;
					curr += 1;
				} else {
					break;
				}
			} else if (arr[curr * 2] < arr[curr * 2 + 1]) {
				if (arr[curr] > arr[curr * 2]) {
					int temp = arr[curr * 2];
					arr[curr * 2] = arr[curr];
					arr[curr] = temp;

					curr *= 2;
				} else {
					break;
				}
			}
		} else {
			if (arr[curr] > arr[curr * 2]) {
				int temp = arr[curr * 2];
				arr[curr * 2] = arr[curr];
				arr[curr] = temp;

				curr *= 2;
			} else {
				break;
			}
		}
	}
}

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

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

	for (int i = 0; i < k; i++) {
		sort();
	}

	printf("%d\n", sorted[k]);

	return 0;
}

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

문제

문제

출처

ICPC

힙소트 구현시 시간초과가 아닌 틀렸습니다. 코드 점검 좀 부탁드리겠습니다.

shfshfdl 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말