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

800

문제는 신입사원들의 서류/면접 성적이 있을 때 이 성적을 사용하여 신입사원을 채용하는 문제이다. 만약 나보다 서류/면접이 모두 좋은 사람이 한사람이라도 있다면 나는 탈락이게 된다. 만약 나의 성적이 [ 4,6 ]인데, 둘 다 나보다 높은 경우 [ 3,5], [ 2,5 ]....가 있으면 나는 탈락되된다. 반대로 [ 2,7 ], [ 3,8 ]의 경우는 내가 하나의 성적은 다른 사람들보다 높게 되므로 이 경우는 합격하게 된다.

 

처음에는 2중 for문으로 한번 풀어봤다. 일단 모든 성적을 입력받은 다음에, N번을 기준으로 N을 제외한 지원자들과 비교해 보았다. 이렇게 하면 지원자의 수가 ~10만 인데, 10^2의 시간복잡도가 나온다. 당연히 시간초과

 

다음 방법은 처음에 입력받을 때, 서류성적을 index로 하고 면접성적을 value로 입력받을 받았다. 1위부터 N위까지 동석차가 없이 결정되기 떄문에 입력받은 배열의 모습은 다음과 같이 된다.

 

입력           배열

3 6             1 4

7 3             2 5

4 2             3 6

1 4              4 2

5 7    -->    5 7

2 5             6 1

6 1              7 3

 

순위는 면접/서류 모두 1위~N까지 이므로, 하나의 성적을 index로 그 index의 값을 다른 하나의 성적으로 하면 위의 배열 모양이 나온다.

이렇게 하는 이유는 문제는 다시 생각해보면, 나의 면접/서류 성적이 다른 지원자의 면접/서류 성적보다 하나라도 높으면 나는 합격이 된다. 

 

여기서는 index=서류 , value=면접 라고 정했으니, 서류에 대하여 오름차순으로 정렬된 모양이다. 이것이 의미하는 것은, 인덱스(서류 성적)2는 1에게 서류 성적에서 졌고, 인덱스3은 2에게 서류 성적에서 졌다는 것이다. 

 

문제 조건에서, 다른 지원자와 비교해서 하나의 성적이라도 높으면 합격이라고 했으니 인덱스2가 1에게 서류 성적에서 졌지만 인덱스 2의 값이 인덱스 1의 값보다 크다면 합격하게 된다. 서류에서는 졌지만, 면접에서는 이겼기 때문이다.

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int j = 0; j < t; j++) {
            int loop = sc.nextInt();
            int[] candidates = new int[loop + 1];
            for (int i = 0; i < loop; i++) {
                candidates[sc.nextInt()] = sc.nextInt();
            }

            int count = 1;
            int interviewRank = candidates[1];

            for (int k = 2; k <= loop; k++) {
                if (interviewRank >= candidates[k]) {
                    interviewRank = candidates[k];
                    count++;
                }
            }

            System.out.println(count);
        }
    }
}