글 읽기 - 계속 시간초과가 뜨네요..ㅜ 도와주십시요!!!

oaojjj 7년 전 0

c언어 여러가지정렬코드가 많던데 그런거 잘 몰라서 그냥 생각나는대로 짜봤는데 계속 시간초과가 뜨네요. ㅜㅜ 방법이없을ㄲㅏ 질문드립니다..

#include<stdio.h>
int num[1000000],num2[1000000];

int main(void) {
	int tmp=0, n, i, j, k, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
	for (j = 0; j < n; j++) {
		cnt = 0;
		for (k = 0; k < n; k++) {
			if (num[j] >= num[k]) {
				cnt++;
			}
		}
		num2[cnt - 1] = num[j];
	}

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

bupjae 7년 전 0

작성하신 알고리즘은 O(n²) 입니다. 100만개 크기의 데이터를 정렬하기 위해서 대략 1조번 연산을 해야 되는데, 이 문제를 풀기에는 너무 느립니다.

심지어 입력 데이터에 동일한 값이 들어오면 제대로 정렬을 할 수 없는 코드입니다.

이 정도 규모의 데이터를 정렬하기 위해 적당한 알고리즘들은 퀵정렬, 병합정렬, 힙정렬 등이 있습니다. 이 중 한 가지를 골라서 공부하신 뒤 다시 작성해 보세요.

bupjae 7년 전 0

윗 글에 첨언: 문제에 수가 중복되지 않는다고 명시되어 있다는 걸 뒤늦게 확인했습니다. 제가 쓴 두 번째 단락은 무시해 주세요.

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

문제

문제

출처

ICPC

계속 시간초과가 뜨네요..ㅜ 도와주십시요!!!

oaojjj 7년 전 0

bupjae 7년 전 0

bupjae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말