1946번 백준 <신입 사원> 그리디 알고리즘

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class GreedyAlgorithm02 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); //테스트 케이스 수

        for(int i = 0; i<T; i++ ){
            int N = Integer.parseInt(br.readLine()); //지원자 수
            int [][] score = new int[N][2]; //각 지원자의 점수
            int count = 1;

            for(int j= 0; j<N; j++){
                String line = br.readLine();
                int pos = line.indexOf(" ");
                score[j][0] = Integer.parseInt(line.substring(0,pos));
                score[j][1] = Integer.parseInt(line.substring(pos+1));
            }

            Arrays.sort(score, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });

            int min = score[0][1];
            for(int j = 1; j<N; j++){
                if(score[j][1] == 1){
                    count++;
                    break;
                }
                if(score[j][1] < min){
                    count++;
                    min = score[j][1];
                }
            }
            System.out.println(count);
        }
    }
}

자꾸 시간 초과 에러가 나서 내 로직이 뭐가 잘못되었는지 몇일간 고민하느라 푸는데 오래걸린 문제!!

 

사실 그 문제는 입력 시간이 너무 길어져서 나는 시간 초과 문제 였다. 

입력하는 함수로 Scanner함수를 사용하였는데, 백준에서 찾아보니 Scanner같은 경우 입력값이 많아질 경우, 시간이 더 오래걸린다고 한다. 

BufferedReader로 바꿔주니 잘 통과 되었다.