[99클럽 5기 코테 스터디 TIL 19일차] 신입 사원 (feat. 탐욕법(Greedy))

1) 문제

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

 

 

2) 풀이

접근 방식

1. 서류심사 성적 기준으로 정렬
   • 서류심사 성적을 기준으로 오름차순 정렬합니다.
   • 그러면 앞에서부터 탐색할 때, 이전에 확인한 지원자보다 서류 성적이 낮은 경우만 확인하면 됩니다.
2. 면접 성적 비교
   • 첫 번째 지원자의 면접 성적을 기준으로 설정합니다.
   • 이후 지원자들의 면접 성적을 비교하면서, 현재까지의 최고 성적보다 낮은 경우 탈락 처리합니다.
   • 면접 성적이 더 높다면 해당 지원자를 선발하고, 최고 면접 성적을 업데이트합니다.
3. 결과 출력
   • 각 테스트 케이스별로 선발할 수 있는 최대 인원을 출력합니다.

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

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

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine()); // 지원자 수
            int[][] applicants = new int[N][2];

            // 지원자 정보 입력
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                applicants[i][0] = Integer.parseInt(st.nextToken()); // 서류심사 성적
                applicants[i][1] = Integer.parseInt(st.nextToken()); // 면접시험 성적
            }

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

            // Greedy 알고리즘 적용
            int count = 1; // 첫 번째 지원자는 무조건 선발
            int bestInterviewRank = applicants[0][1]; // 첫 번째 지원자의 면접 순위

            for (int i = 1; i < N; i++) {
                if (applicants[i][1] < bestInterviewRank) { // 면접 순위가 더 높다면 선발 가능
                    count++;
                    bestInterviewRank = applicants[i][1]; // 최고 면접 순위 업데이트
                }
            }

            sb.append(count).append("\n");
        }

        System.out.print(sb);
    }
}