글 읽기 - 시간초과 질문이요

dudxksdl11 6년 전 0

무슨이유때문에 시간초과가 나는지 모르겠어서 알려주시면 감사하겠습니다ㅎㅎ

#include<stdio.h>

long long N[1000001];

int main(){
	long long n,tmp,i,j;
	
	scanf("%lld",&n);
	
	for(i=0;i<n;i++)
	{
			scanf("%lld",&N[i]);
			tmp=N[i];
			for(j=i-1;j>=0;j--)
			{
				if(tmp<N[j])	
					N[j+1]=N[j];
				else
					break;	
			}
			N[j+1]=tmp;
	}
	
	for(i=0;i<n;i++)
		printf("%lld\n",N[i]);

	return 0;	
}

joonas 6년 전 1

지금 작성한 코드는 O(N^2) 이라서 최악의 경우 N=1,000,000 이라면 O(N^2) = 10^12 입니다.

문제의 제한시간 안에 정렬되기는 힘들겠네요.

joonas 6년 전 1

내장 라이브러리의 정렬 함수들(http://en.cppreference.com/mwi...)을 사용하거나 더 빠른 정렬 알고리즘을 직접 구현해보세요.

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

문제

문제

출처

ICPC

시간초과 질문이요

dudxksdl11 6년 전 0

joonas 6년 전 1

joonas 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말