[알고리즘]백준1946 신입사원 -java

1. 문제

2. 생각

첫번째 생각

1. 지원자의 수만큼의 크기로 이중배열을 만든다. work[신입사원 수][2];
2. 지원자의 점수랑 다른 모든 지원자의 순위를 비교한다.
3. 현재 검사하는 지원자의 서류,면접순위보다 둘다 높은 지원자가 있다면 채용인원에서 제외한다.
4. 전체 지원자-제외인원을 출력

결과 : 시간초과

최대 테스트 수 20, 최대지원자 수 100,000 시간 제한 2초

시간복잡도 계산시 T*(n^2)가 나온다.
최대지원자가 100,000이기 때문에 n=100,000대입하면 최대 100초가 나오므로 시간초과

두번째 생각

1. 지원자의 수만큼의 크기로 이중배열을 만든다. work[신입사원 수][2];
2. 서류성적을 먼저 오름차순으로 정렬한다.
3. 서류성적 1등의 면접순위과 2등부터 차례로 지원자의 면접순위을 비교하여 면접순위가 더 높은 경우 선발한다.
4. 선발된 사람의 면접순위로 기준을 바꾼다.

결과 : 시간초과

Arrays.sort()로 정렬했는데 최악의 경우 n^2이다.
n=100,000대입할 경우 정렬만으로 100억=100초가 걸리므로 시간초과

세번째 생각

1. 지원자의 수만큼의 크기의 배열을 만든다.
2. 배열의 인덱스에는 서류순위을, 값에는 면접순위을 입력받는다.
3. 서류성적 1등의 면접순위과 2등부터 차례로 지원자의 면접순위을 비교하여 면접순위가 더 높은 경우 선발한다.
4. 선발된 사람의 면접순위로 기준을 바꾼다.

결과 : 성공

순위는 중복되지 않는다 라는것을 이용해 인덱스를 서류성적으로 이용했다.
이럴 경우 정렬할 필요가 없기 때문에
시간복잡도 : n 이된다.

3. 코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class baekjoon1946 {
    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);

        int n= scan.nextInt();

        for(int i=0;i<n;i++){
            int m=scan.nextInt();
            int count=1;
            int work[]=new int[m+1];
            for(int j=0;j<m;j++){
                int a=scan.nextInt();
                int b=scan.nextInt();
                work[a]=b;
            }

            int vot= work[1];

            for(int j=2;j<=m;j++){
                if(work[j]<vot){
                    vot=work[j];
                    count++;

                }
            }
            System.out.println(count);



        }
        scan.close();
    }
}