[백준] 1946번: 신입 사원(그리디, 정렬)

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

1946번: 신입 사원

 

틀린 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int tc=0; tc<T; tc++) {
			int N = scan.nextInt();	// 지원자 숫자
			int[][] arr = new int[N][2];	// 각 지원자의 서류, 면접 성적
			int count = N;			// 선발할 수 있는 신입사원의 최대 인원수
			
			for(int i=0; i<N; i++) {
				arr[i][0] = scan.nextInt();	
				arr[i][1] = scan.nextInt();
			}
			
			// 지원자 별로 서류 or 면접 심사 판단하기
			for(int i=0; i<N; i++) {
				boolean docu = true;	// 서류심사 판단
				boolean pt = true;		// 면접심사 판단
				
				for(int j=0; j<N; j++) {	// 서류심사 성적 판단
					if(arr[i][0] < arr[j][0]) {	// 자신보다 서류 성적이 떨어지는 인원이 있을경우(숫자가 더 클경우)
						docu = false;
						break;
					}
				}
				
				for(int j=0; j<N; j++) {	// 면접심사 성적 판단
					if(arr[i][1] < arr[j][1]) {	// 자신보다 면접 성적이 떨어지는 인원이 있을경우(숫자가 더 클경우)
						pt = false;
						break;
					}
				}
				
				// 서류, 면접 성적 모두 자신보다 떨어지는 인원이 없을경우 => 선발 X
				if(docu == true && pt == true) {
					count --;
				}
			}
			
			System.out.println(count);
		}
		
		scan.close();
	}

}

 

풀이

문제를 이해하는데에도 오래걸렸다... 입력받는게 점수가 아닌 순위 등수이다.

따라서 입력이 1, 5가 있다면 5가 아닌 1이 더 높은 성적이다.(순위)

문제에서 지원자 A와 다른 모든 지원자 B의 서류심사 성적과 면접시험 성적을 비교했을때, 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않아야 선발을 한다. 지원자가 5명인 경우의 예를 들어보자.

 

A: 3  2

B: 1  4

C: 4  1

D: 2  3

E: 5  5

 

A, B, C, D, E 5명의 지원자가 있고, 서류와 면접 성적이 위와 같을때, 위에서 지원자 E는 결코 선발되지 않는다.

숫자가 등수를 의미하므로, E의 서류 성적과 면접 성적은 다른 지원자들에 비해 모두 떨어진다.

 

지원자가 7명인 경우의 예를 들어보면,,

A: 3  6

B: 7  3

C: 4  2

D: 1  4

E: 5  7

F: 2  5

G: 6  1

 

위와 같이 있을때,

지원자 A는 지원자 D와 비교했을 때, 서류성적과 면접성적이 모두 떨어지므로 선발을 할 수 없다.

지원자 B는 지원자 C와 비교했을 때, 서류성적과 면접성적이 모두 떨어지므로 선발을 할 수 없다.

지원자 E는 지원자 D와 비교했을 때, 서류성적과 면접성적이 모두 떨어지므로 선발을 할 수 없다.

지원자 F는 지원자 D와 비교했을 때, 서류성적과 면접성적이 모두 떨어지므로 선발을 할 수 없다.

따라서 선발 할 수 있는 인원은 C, D, G 3명의 지원자이다.

 

위 코드에서는, 서류 성적과 면접 성적을 따로따로 비교했고, 비교 조건도 틀렸다.

 

 

틀린 코드2

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int tc=0; tc<T; tc++) {
			int N = scan.nextInt();	// 지원자 숫자
			int[][] arr = new int[N][2];	// 각 지원자의 서류, 면접 성적
			int count = N;			// 선발할 수 있는 신입사원의 최대 인원수
			
			for(int i=0; i<N; i++) {
				arr[i][0] = scan.nextInt();	
				arr[i][1] = scan.nextInt();
			}
			
			// 지원자 별로 서류, 면접 성적 비교
			for(int i=0; i<N; i++) {
				boolean flag = true;
				
				for(int j=0; j<N; j++) {
					// 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류, 면접 성적이 모두 떨어질때
					// 숫자가 큰게 등수가 낮음.
					if(arr[i][0] > arr[j][0] && arr[i][1] > arr[j][1]) {	
						flag = false;
						break;
					}
				}
				
				// 서류, 면접 성적 모두 자신보다 떨어지는 인원이 없을경우 => 선발 X
				if(!flag) 
					count --;
			}
			
			System.out.println(count);
		}
		
		scan.close();
	}

}

 

위 코드는 지원자들 끼리 비교를 해서, 만약 지원자 A가 임의의 지원자보다 서류 성적, 면접 성적이 모두 떨어질경우

					// 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류, 면접 성적이 모두 떨어질때
					// 숫자가 큰게 등수가 낮음.
					if(arr[i][0] > arr[j][0] && arr[i][1] > arr[j][1]) {	
						flag = false;
						break;
					}

선발될 수 없으므로 count--를 해주었는데 ...

 

 

시간 초과가 발생했다 ...

 

지원자의 숫자가 최대 100,000명 이므로 모든 지원자수를 비교하기에 시간초과가 발생한다 ..

 

 

 

최종 코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int tc=0; tc<T; tc++) {
			int N = scan.nextInt();	// 지원자 숫자
			int[][] arr = new int[N][2];	// 각 지원자의 서류, 면접 성적
			int count = 1;			// 정렬의 첫 번째 사람은 자동 채용
			for(int i=0; i<N; i++) {
				arr[i][0] = scan.nextInt();	
				arr[i][1] = scan.nextInt();
			}
			
			// 정렬 - Comparator
			Arrays.sort(arr, new Comparator<int[]>() {
				@Override
				public int compare(int[] arr1, int[] arr2) {	// 서류를 기준으로 오름차순 정렬을 시행한다.
					return Integer.compare(arr1[0], arr2[0]);
				}
			});
			
			int pivot = arr[0][1];	// 첫 번째 지원자의 면접 성적이 기준이 된다.
			for(int i=1; i<N; i++) {
				if(arr[i][1] < pivot) {	// 면접 성적이 그 전 선발된 지원자 보다 뛰어날경우 => 선발
					pivot = arr[i][1];	// 다음 합격자를 판별하기 위해 전에 선발된 지원자의 면접 성적 저장
					count ++;
				}
			}
			System.out.println(count);
		}
		scan.close();
	}
}

 

풀이

문제에서 동석차 없이 결정된다고 가정해서 한 성적은 정렬을 하고, 나머지 성적으로 비교를 해야 할 것 같다는 생각은 들었지만,, 결국 해결은 못했다.

위 풀이는 지원자의 서류 순위와 면접 순위중 서류 순위는 오름차순으로 정렬을 하고, 면접 순위로 지원자가 선발이 될 수 있는지 없는지 판단한다.

 

N = 7 을 기준으로 예를 들면서 보자.

위 그림을 보면, 서류 순위를 기준으로 오름차순을 정렬한다.

첫 번째 지원자의 경우 서류 순위로 1위이기 때문에, 무조건 선발이 된다.

따라서 두 번째 지원자부터 비교를 해주면 된다.

이 때, 서류 순위의 경우 오름차순 정렬이므로, 아래로 갈수록 밀리게(떨어지게) 된다.

따라서 비교를 진행할 때, 가장 최근 채용된 지원자의 면접 순위보다 높은 지원자를 찾아야 한다.

 

두 번째 지원자의 경우, 첫 번째 지원자보다 서류 순위도 떨어지고 면접 순위도 떨어진다. 따라서 선발 X

세 번째 지원자의 경우 마찬가지 둘 다 떨어지므로 선발 X

네 번째 지원자의 경우, 서류 순위는 떨어지나 면접 순위에서 성적이 높으므로 선발이 된다.

다섯번째 지원자의 경우, 면접 순위가 꼴찌이므로 당연히 선발 X

여섯번째 지원자의 경우, 면접 순위가 1위이므로 선발이 된다.

마지막 지원자의 경우, 면접 순위에서 이전에 채용된 네 번째, 여섯번째 지원자보다 떨어지므로 선발 X

 

따라서 총 채용자는 3명이다.