[Baekjoon Online Judge] 1946번: 신입 사원

1946번: 신입 사원

1946번: 신입 사원

 처음 이 문제를 접했을 때 이해하는데 조금 시간이 걸렸다. 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선별한다는 원칙이 잘 이해가 되지 않았다. 

 

예시를 들어보면,

서류심사 순위	면접시험 순위
3	2
1	4
4	1
2	3
5	5

 

각각의 지원자의 서류심사 성적 순위와 면접시험 성적 순위가 위 표와 같은 경우, 서류심사를 기준으로 우선 정렬하였다.

 

서류심사 순위	면접시험 순위
1	4
2	3
3	2
4	1
5	5

정렬을 마치게 되면 서류심사는 이미 비교가 끝나게 된다. 이제 면접시험 순위를 비교하기 위해 1순위의 면접시험 순위를 찾아가며 합격자 수를 늘리면 된다. 처음 tempGrade는 4부터 시작한다. 3과 비교하면, 2, 3 지원자는 합격 기준에 만족한다. 그 다음 tempGrade에 3을 저장한다. 그 다음 3과 2를 비교하면 3, 2 지원자 또한 합격하게 된다. 이것을 반복하면 5,5 지원자를 제외하고 전원 합격하게 된다.

 

import java.io.*;
import java.util.Arrays;

public class Baekjoon1946 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(bufferedReader.readLine()); // 테스트 케이스의 개수

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bufferedReader.readLine()); // 지원자의 숫자

            int[][] grades = new int[n][2];
            for (int j = 0; j < n; j++) {
                String[] gradeSplit = bufferedReader.readLine().split(" ");
                grades[j][0] = Integer.parseInt(gradeSplit[0]); // 서류심사 순위
                grades[j][1] = Integer.parseInt(gradeSplit[1]); // 면접시험 순위
            }

            // 서류심사 순위에 대해서 오름차순으로 정렬
            Arrays.sort(grades, (x, y) -> {
                return Integer.compare(x[0], y[0]);
            });

            int count = 1; // 서류심사 순위 기준 1순위 합격자 1명 부터 시작
            int tempGrade = grades[0][1]; // 서류심사 순위 기준 1순위의 면접시험 순위를 tempGrade 에 저장
            for (int j = 1; j < grades.length; j++) {
                if (grades[j][1] < tempGrade) {
                    // 서류심사 순위를 정렬했기 때문에 더이상 고려대상이 아니다.
                    // if 현재 지원자의 면접시험 순위가 임시로 저장된 면접시험 순위보다 작으면
                    // 합격자 수가 늘어나고 해당 합격자의 면접시험 순위가 들어간다.
                    ++count;
                    tempGrade = grades[j][1];
                }
            }
            bufferedWriter.write(String.valueOf(count) + "\n");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}