[백준 1946] 신입 사원

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

1946번: 신입 사원

 

1. 풀이

---

문제의 조건은 A라는 사람의 서류 및 면접 시험의 성적이 B라는 사람 보다 둘 다 열세라면 채용을 하지 않는다는 것이엇습니다.

 

따라서 그리디를 사용하였고, 아래와 같이 풀이를 하였습니다.

 

1. 서류심사의 성적을 기준으로 오름차순 정렬

2. 정렬후 첫번째는 서류가 1등이므로 무조건 채용, 그리고 첫번째 면접 시험을 저장합니다.

3. 반복문을 돌리면서 저장한 면접 시험의 최저순위보다 우위인 사람을 채용합니다.

 

2. 코드

---

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		for(int i = 0; i < n; i++) {
			int num_case = sc.nextInt();
			int arr[][] = new int[num_case][2];
			for(int j = 0; j < num_case; j++) {
				arr[j][0] = sc.nextInt();
				arr[j][1] = sc.nextInt();
			}
			
			// 정렬 ( 앞을 기준으로 정렬 )
			Arrays.sort(arr, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return Integer.compare(o1[0], o2[0]);
				}
			});
			
			int min = 0;
			int result = 0;
			for(int k = 0; k < num_case; k++) {
				if(k == 0)
					min = arr[k][1]+1;
				if(arr[k][1] < min) {
					result++;
					min = arr[k][1];
				}
			}
			System.out.println(result);
		}
		
		sc.close();
		return;
	}
}