글 읽기 - 2751번 시간초과

ieebom 5년 전 0

디버깅은 돼는데 뭐가 틀렸는지 모르겠네요 ㅜㅜ

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int i;
	int n = 0;
	cin >> n;
	int sort[1000000];
	int input = 0;
	int temp = 0;
	

	for (i = 0; i < n; i++)
	{
		cin >> input;
		sort[i] = input;
	}

	for(i=0;i<n;i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (sort[i] > sort[j])
			{
				temp = sort[i];
				sort[i] = sort[j];
				sort[j] = temp;
			}
		}
		cout << sort[i] << endl;
	}
	
	return 0;
}

kimsy96 5년 전 0

입력으로 주어지는 수의 개수가 최대 백만개입니다

버블소트 O(n^2)로는 시간초과가 납니다

더 빠른 정렬이 필요합니다

apjw6112 5년 전 1

퀵 소트를 구현하거나 함수를 이용해서 쓰세요.

버블 소트는 앞에서 말했듯이 시간복잡도가 O(N^2)인데 퀵 소트는 시간복잡도가 O(NlogN)이기 때문에 빠른 시간 내에 정렬을 할 수 있습니다.

sk251525 5년 전 1

qsort 또한 가능하더군요,,

시간복잡도를 더 확실히 줄이고 싶다면

STL SORT 를 써서 O(n log n) 만에 처리하시는 것도 좋은 방법입니다.

버블소트는 O(n*n)시간복잡도이기때문에 1000000개의 입력은 당연히 시간초과가 납니다. 위에서 말하듯이 퀵소트는 (nlogn)이라 더빠릅니다. 하지만 퀵소트 역시 시간초과가 나야 정상입니다. 퀵소트 경우 모두 정렬된 입력이 들어올경우 최악의 시간복잡도는 (n*n)이 되어 버립니다. 결국 모든 경우를 다 돌려보면 시간초과가 나는 경우가 생깁니다. 그러므로 버블소트,,,퀵소트도 아닌 머지소트나 힙소트를 사용하시기 바랍니다.

apjw6112 5년 전 0

저는 함수 써서 풀었습니다.

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

문제

문제

출처

ICPC

2751번 시간초과

ieebom 5년 전 0

kimsy96 5년 전 0

apjw6112 5년 전 1

sk251525 5년 전 1

wlshddlek 5년 전 3

apjw6112 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말