[백준] 1946 신입 사원 - 탐욕법(Greedy) + 정렬(Sort) JAVA

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

코드설명

탐욕법(Greedy) + 정렬(Sort) 을 활용합니다.

 

어떻게 탐욕적으로 작성해야할지, 현재 상황에서 최선의 선택을 할지 아이디어를 떠올리는것이 어려웠습니다.

 

코드 로직입니다.

1. 서류점수를 기준으로만 해서 (서류점수, 면접점수)를 정렬합니다.

이렇게 되면 서류점수 1등을 기준으로, 서류점수1등보다 2 3 4 5 6 7.. 등은 모두 서류점수가 낮은것이므로 면접점수가 반드시 높아야합니다.

2. 면접점수를 비교하기 시작합니다.

이때, 유의할사항은, 서류점수 1등의 면접점수보다 더 높은 면접점수를 가진 사람이 등장할때마다, minInterviewRank, 다음사람이 통과해야할 서류점수가 더 높아진다는 것 입니다. 

이유는, 서류등수가 오름차순으로 정렬되어있기에 이번에 연산하는 사람은 이전 연산하는 사람보다 더 낮은 서류점수를 가지고 있으므로 적어도 면접 점수는 더 높아야한다는 것 입니다. 그래야만 

" 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다 " 이 규칙을 지킬 수 있는 것이지요. 이 과정을 통해 "지금까지 선발된 지원자들 중 가장 좋은 면접순위"를 계속해서 갱신해나가며, 다음번의 서류면접점수가 상대적으로 낮은 지원자가 해당 면접순위보다 높아야만 들어올 수 있도록 처리합니다.

 

즉, 어떻게 보면 서류점수로 먼저, 필터링한뒤 면접점수로 필터링한다라고 생각하면 될 것 같습니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static int[][] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			arr = new int[N][2];
			for(int i=0;i<N; i++) {
				st = new StringTokenizer(br.readLine());
				arr[i][0] = Integer.parseInt(st.nextToken());
				arr[i][1] = Integer.parseInt(st.nextToken());
			}
			//서류점수로 오름차순 정렬합니다.
			Arrays.sort(arr, 0, N, new Comparator<int[]>() {
				@Override
				public int compare(int[] a, int[] b) {
					return Integer.compare(a[0], b[0]);
				}
			});
			
			//서류점수에서 오름차순 정렬한뒤, 서류점수 1등인 사람의 면접점수를 가져옵니다.
			answer = 1;
			int minInterviewRank = arr[0][1];
			for(int i=1; i<N; i++) {
				if(minInterviewRank > arr[i][1]) {
					answer += 1;
					minInterviewRank = arr[i][1];
				}
			}
			System.out.println(answer);
		}
		
	}
	

}