println은 출력시마다 버퍼를 비워야해서 print(b[i] + '\n') 보다 느립니다.
그리고 scanner보다는 bufferedreader로 읽는 게 더 빠릅니다.
둘을 조합하니 시간 초과는 면하는데 오답이 나오네요.
11931번 - 수 정렬하기 4
println은 출력시마다 버퍼를 비워야해서 print(b[i] + '\n') 보다 느립니다.
그리고 scanner보다는 bufferedreader로 읽는 게 더 빠릅니다.
둘을 조합하니 시간 초과는 면하는데 오답이 나오네요.
@indioindio 님..
덕분에 조합으로 시간초과는 해결했는데요 ㅎㅎㅎㅎㅎㅎ 런타임에러가 나오는 이유를 혹시 아시나요 감이 안잡히네요 ㅠㅠ;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String args[]) throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int num=(Integer.parseInt(st.nextToken()));
int[] a = new int[num];
int[] b = new int[num];
for(int i = 0; i < num; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
countingSort(a,b,num);
for(int i = num-1; i>=0; i--) {
System.out.print(b[i]+"\n");
}
}
public static void countingSort(int a[],int b[],int num){
int k=2000001;
int d=k/2;
int c[] = new int[k];
for(int i=0;i<k;i++)
c[i]=0;
for(int j=0;j<num;j++)
c[a[j]+d]++;
for(int i=1;i<k;i++)
c[i]=c[i]+c[i-1];
for(int j=num-1;j>=0;j--){
b[c[a[j]+d]-1]=a[j];
c[a[j]+d]--;
}
}
}
댓글을 작성하려면 로그인해야 합니다.
chucky3 8년 전
countingSort 를 이용하여 O(n) 의 시간복잡도를 사용했는데
5%에서 시간초과가 나오네요..
자료의 수와 시간복잡도가 어느정도일때 몇초가 걸리는지도 혹시 알 수 있을까요..