chucky3   7달 전

countingSort 를 이용하여 O(n) 의 시간복잡도를 사용했는데

5%에서 시간초과가 나오네요..

자료의 수와 시간복잡도가 어느정도일때 몇초가 걸리는지도 혹시 알 수 있을까요..

indioindio   7달 전

println은 출력시마다 버퍼를 비워야해서 print(b[i] + '\n') 보다 느립니다.

그리고 scanner보다는 bufferedreader로 읽는 게 더 빠릅니다.

둘을 조합하니 시간 초과는 면하는데 오답이 나오네요.

chucky3   7달 전

ㅋㅋ 오름차순 내림차순 때문에 오답나온 것 같아요 문제 해결됐습니다 감사합니다 ~

chucky3   7달 전

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]--;
        }
    }
}

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