[BaekJoon] 1946 신입 사원

1.  문제 링크

2.  문제

요약

• 진영 주식회사에서는 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발하려고 합니다.(지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류심사 결과와 면접 성적이 모두 떨어진다면 A는 선발되지 않습니다.)
• 지원자의 수와 각 지원자의 서류심사 성적과 면접 성적이 주어질 때 위 조건을 만족시키면서 진영 주식회사가 신입사원으로 선발할 수 있는 최대 인원수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스의 첫 번째 줄에는 1보다 크거나 같고 100,000보다 작거나 같은 지원자의 수 N이 주어지며 각 테스트 케이스의 두 번째 줄부터 N개의 줄에는 각 지원자의 서류심사 성적, 면접 성적의 순위가 주어집니다.(두 성적 순위는 1위부터 N위까지 동석차 없이 결정됩니다.)
• 출력: 첫 번째 줄부터 T개의 줄에 각 테스트 케이스에 대한 선발할 수 있는 신입사원의 최대 인원수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	public int getMaxWorkerNum(Worker[] workers) {
		Arrays.sort(workers, new Comparator<Worker>() {
			public int compare(Worker w1, Worker w2) {
				return w1.documentation - w2.documentation;
			}
		});
		int count = 1;
		int prev_interview = workers[0].interview;
		for(int i = 1; i < workers.length; i++) {
			if(prev_interview > workers[i].interview) {
				count++;
				prev_interview = workers[i].interview;
			}
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int test_num = Integer.parseInt(br.readLine());
		int[] maxWorkerNum = new int[test_num];
		Main m = new Main();
		for(int i = 0; i < test_num; i++) {
			int worker_num = Integer.parseInt(br.readLine());
			Worker[] workers = new Worker[worker_num];
			for(int j = 0; j < workers.length; j++) {
				String[] input = br.readLine().split(" ");
				workers[j] = new Worker(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
			}
			maxWorkerNum[i] = m.getMaxWorkerNum(workers);
		}
		br.close();
		for(int i = 0; i < maxWorkerNum.length; i++) {
			bw.write(maxWorkerNum[i] + "\n");
		}
		bw.flush();
		bw.close();
	}
}

class Worker {
	int documentation;
	int interview;
	public Worker(int documentation, int interview) {
		this.documentation = documentation;
		this.interview = interview;
	}
}

4.  접근

• 이 문제는 서류심사 성적과 면접 성적 중 하나라도 다른 사람보다 높으면 뽑을 수 있기 때문에 둘 중 하나를 기준으로 정렬한 후에 가장 순위가 높은 사람부터 차례대로 내려오면서 자신보다 순위가 높은 사람들 중에서 가장 기준이 아닌 다른 성적이 좋은 사람과 자신의 성적을 비교하여 자신이 그 성적보다 높다면 채용될 수 있는 사람이므로 이러한 사람들의 수를 구하면 되는 문제입니다.

1. 각 지원자들의 서류심사 성적과 면접 성적을 담을 Worker라는 class를 만들고 주어진 입력에 따라 workers라는 1차원 배열에 각 지원자들의 정보를 담은 Worker 객체들을 설정합니다.
2. 두 성적 중 한 가지 성적을 기준으로 삼아 정렬합니다. 저는 서류심사 성적을 기준으로 정렬하였습니다.
3. 채용될 수 있는 지원자의 수를 나타내는 count라는 변수를 생성하고 서류심사 기준으로 정렬된 지원자들 중 가장 서류심사 성적이 높은 지원자는 채용될 수 있는 지원자이기 때문에 count에는 1을 설정해주고 현재 지원자 이전까지의 지원자들 중에서 가장 높은 면접 성적을 담을 prev_interview라는 변수를 생성하여 가장 서류심사 성적이 높은 지원자의 면접 성적을 설정합니다.
4. 두 번째로 서류심사 성적이 좋은 지원자부터 마지막 지원자까지 돌면서 현재 지원자의 면접 성적이 이전까지의 지원자들 중 가장 높은 면접 성적보다 더 좋은 성적이라면 count 변수에 1을 추가해주고 prev_interview 변수의 값을 현재 지원자의 면접 성적으로 변경합니다.
5. 4번에서 모든 지원자를 다 확인하고 나서의 count 값이 선발할 수 있는 신입사원의 최대 인원수가 되기 때문에 이를 출력합니다.