백준알고리즘 1946번 신입사원

문제링크

그리디 알고리즘을 이용한 것으로 

서류 심사를 오름 차순으로 정렬한다.

3 2
1 4
4 1
2 3
5 5

1 4
2 3
3 2
4 1
5 5

1등의 면접 시험을 기준으로 크면 탈락 작으면 채용 성공을 하게 하고 면접 시험 기준을 기준으로 삼는다.

아래 소스는 시간 초과 발생. 답은 정말잘나오는데 원인은 무엇일까 ?

정렬 알고리즘을 바꿔야 한다. 최악의 조건을 가정하여.

정렬 알고리즘 바꾸는건 스스로 해보시기를 ㅠㅠㅠㅠㅠ

import java.io.IOException;
import java.util.Scanner;

//신입 사원
public class NewComer {
    static int testCase;
    static int person;
    static int[][] testResult;
    static int[] selectPerson;
    static Scanner scan;
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        scan = new Scanner(System.in); // 문자 입력을 인자로 Scanner 생성
        testCase = Integer.parseInt(scan.nextLine().trim()); // 키보드 문자 입력
        selectPerson = new int[testCase]; // 테스트 케이스별로 뽑힌 인원 저장하는 배열
        
        // 테스트 케이스
        for (int i = 0; i < testCase; i++) {
            int result = 0; // 테스트 케이스별로 뽑힌 인원의 수를 나타낸다.
            
            person = Integer.parseInt(scan.nextLine().trim()); // 키보드 문자 입력
            testResult = new int[person][2];
            // 시험 성적 입력
            for (int j = 0; j < person; j++) {
                testResult[j][0] = scan.nextInt();
                testResult[j][1] = Integer.parseInt(scan.nextLine().trim());
            }
            //배열을 기준으로 성적을 오름차순으로 정리
            testResultSort(testResult);

            for (int s = 1; s < person; s++) {
                int index = testResult[s][1];
                Boolean circle = true;
                for (int k = 0; k < s; k++) {
                    if (circle && testResult[k][1] > index) {
                        circle = true;
                    }else
                        circle = false;
                }
                if(circle)
                    result +=1;
            }
            selectPerson[i] = result+1;

        }
        
        for(int i=0;i<selectPerson.length;i++)
            System.out.println(selectPerson[i]);
        
    }

    
    public static void testResultSort(int[][] array) {
        for (int index = 1; index < array.length; index++) {
            
            int tmp = array[index][0];
            int tmp1 = array[index][1];
            int dif = index - 1;

            while ((dif >= 0) && (array[dif][0] > tmp)) {
                array[dif + 1][0] = array[dif][0];
                array[dif + 1][1] = array[dif][1];
                dif--;
            }       
            array[dif + 1][0] = tmp;
            array[dif + 1][1] = tmp1;
        }
    }

}