백준 1260번: 신입사원

문제 분석

1. 조건 해석:
   • 각 지원자는 서류 성적과 면접 성적을 가지고 있습니다.
   • 두 지원자 A와 B가 있을 때, A가 B보다 서류 성적과 면접 성적이 모두 떨어지면 A는 선발되지 않습니다.
   • 이 조건을 만족하는 최대 선발 인원수를 구하는 문제입니다.
2. 핵심 아이디어:
   • 서류 성적을 기준으로 정렬한 후, 면접 성적을 기준으로 선발 가능성을 확인합니다.
   • 즉, 서류 성적이 좋은 순서대로 정렬하고, 그 뒤에서 면접 성적이 좋거나 나쁜지 확인하면서 선발 조건을 만족하는지 검사합니다.
   • 면접 성적은 서류 성적 순으로 진행되므로, 면접 성적이 이전 지원자보다 더 좋으면 선발될 수 있습니다.

 

알고리즘 흐름

1. 서류 성적을 기준으로 정렬합니다.
2. 서류 성적 순으로 진행하면서, 면접 성적이 이전 면접 성적보다 좋다면 해당 지원자는 선발됩니다.
3. 최종적으로 선발된 지원자 수를 출력합니다.

 

코드 구현

import java.util.*;

public class Main {

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

        int T = sc.nextInt(); // 테스트 케이스 수
        while (T-- > 0) {
            int N = sc.nextInt(); // 지원자 수
            int[][] applicants = new int[N][2]; // 지원자의 서류 성적과 면접 성적

            for (int i = 0; i < N; i++) {
                applicants[i][0] = sc.nextInt(); // 서류 성적
                applicants[i][1] = sc.nextInt(); // 면접 성적
            }

            // 서류 성적 기준으로 오름차순 정렬
            Arrays.sort(applicants, (a, b) -> a[0] - b[0]);

            int count = 1; // 첫 번째 지원자는 무조건 선발
            int bestInterview = applicants[0][1]; // 첫 번째 지원자의 면접 성적

            for (int i = 1; i < N; i++) {
                // 현재 지원자의 면접 성적이 이전에 선발된 지원자보다 좋으면 선발
                if (applicants[i][1] < bestInterview) {
                    count++;
                    bestInterview = applicants[i][1];
                }
            }

            System.out.println(count); // 선발된 지원자의 수 출력
        }
    }
}

 

 

시간 복잡도

• 각 테스트 케이스마다 서류 성적을 기준으로 N개의 지원자를 정렬하므로 정렬 시간은 O(N log N)입니다.
• 그 후에 한 번의 선발 과정에서 N개의 지원자를 순차적으로 확인하므로 시간 복잡도는 O(N)입니다.
• 따라서 각 테스트 케이스의 시간 복잡도는 O(N log N)입니다.