1517번 - 버블 소트
#include<stdio.h>#include<stdlib.h>
int main(void){ int N,i,x,t,sum=0; scanf("%d",&N); int *A=(int*)malloc(sizeof(int)*N); for(i=0;i<N;i++) scanf("%d",&A[i]); for(t=0;t<N-1;t++) { for(i=0;i<N-1;i++) { if(A[i]>A[i+1]) { x= A[i]; A[i]=A[i+1]; A[i+1]=x; sum++; } } } printf("%d\n",sum); return 0;
}
왜 시간초과 나오는건가요 도저히 모
250000000000번 반복하면 1초 안에 불가능해요
죄송하지만 구체적으로 설명해주실 수 있을까요??
N이 최대 500000이고 버블정렬의 시간복잡도는 O(N2)입니다.즉 N2번 반복한다는 것이지요. 그런데 5000002 즉 250000000000번 반복하면 1초를 넘는 것이 대부분입니다.
댓글을 작성하려면 로그인해야 합니다.
amm7931 7년 전
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int N,i,x,t,sum=0;
scanf("%d",&N);
int *A=(int*)malloc(sizeof(int)*N);
for(i=0;i<N;i++)
scanf("%d",&A[i]);
for(t=0;t<N-1;t++)
{
for(i=0;i<N-1;i++)
{
if(A[i]>A[i+1])
{
x= A[i];
A[i]=A[i+1];
A[i+1]=x;
sum++;
}
}
}
printf("%d\n",sum);
return 0;
}
왜 시간초과 나오는건가요 도저히 모