sse8210   7년 전

자꾸 시간초과가 나요

for 문 많이도 안도는데 ㅠㅠㅠ

처음 해보는데 어렵네요


로직은 2차원 배열에 자료를 넣고

왼쪽 등수로 정렬한후에

뒷쪽 등수를 기준으로 비교하는 로직입니다.
 
public class Main {
    static int T;
    static int N;
    static int count;
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
 
 
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            {
                int N = sc.nextInt();
                int sin[][] = new int[N][2];
                // 정렬에 넣기
                for (int j = 0; j < N; j++) {
                    sin[j][0] = sc.nextInt();
                    sin[j][1] = sc.nextInt();
                }
                // 왼쪽이 작은것부터 정렬하기
                int temp;
                int temp2;
 
                for (int k = 0; k < N - 1; k++) {
                    for (int l = k + 1; l < N; l++) {
                        if (sin[l][0] <= sin[k][0]) {
                            temp = sin[l][0];
                            temp2 = sin[l][1];
                            sin[l][0] = sin[k][0];
                            sin[l][1] = sin[k][1];
                            sin[k][0] = temp;
                            sin[k][1] = temp2;
                            // System.out.println(sin);
                        }
 
                    }
                }
                // 정렬 끝
 
                int c = sin[0][1];
                count = 1;
                for (int i = 1; i < N; i++) {
                    if (sin[i][1] < c) {
//                      System.out.println(c);
//                      System.out.println(sin[i][1]);
                         
                        c = sin[i][1];
                        count = count + 1;
//                      System.out.println(count);
                    }
                }
 
                System.out.println(count);
 
            }
 
 
        }
        
    }
 
}

zlzmsrhak   7년 전

숫자 개수가 10만개 일 때 반복분 2개면 약 100초 정도 걸린다고 생각하시면 됩니다.

연산 횟수가 1억번 정도일 때 약 1초정도 걸린다고 생각하면, 정렬에만 10만 * 10만 / 1억 = 100초 정도가 걸립니다.

O(N lg N) 정도의 시간복잡도를 가지는 정렬 알고리즘을 사용하여야 합니다.

sse8210   7년 전

감사합니다.

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