[ 알고리즘 ] 코딩 - 백준 1946 - 신입사원.java

---

문제 링크

www.acmicpc.net/problem/1946

1946번: 신입 사원

---

문제 개요

BOJ 1946 - (자바) 신입사원 - 그리디(탐욕기법)

 

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

 

---

로직

일반 정렬을 사용해도 풀리지만 시간이 너무 많이 걸려서 놀랐다. 정렬을 사용하지 않고 1차원 배열을 인덱스를 이용해서 적절하게 사용하면 정렬을 하지 않고도 해결할수있다! 하지만 여기서는 우선순위큐로 정렬해서 구현했다!

Step 01. 우선순위큐의 정렬 규칙을 앞의 성적으로 내림차순으로 잡고 입력을 받는다. 

Step 02. 가장 앞에 있는 지원자는 서류 1등이므로 무조건 합격이다. 이 합격자를 기준으로 다음 합격자와 비교하자. 

현재 지원자가 이전 합격자의 서류 점수와 면접 점수가 둘 다 낮다면 다음 지원자를 확인하자. 만약 하나라도 높다면 현재 지원의 성적을 다음 지원자의 성적의 지표로 삼자.

Step 03. Step 02를 N-1번 반복해서 누적된 인원수가 정답.

 

그리디라서 방법만 알면 구현할 수 있다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			
			PriorityQueue<int[]> pQueue = new PriorityQueue<int[]>((o1, o2) -> (o1[0] - o2[0]));
			for(int i = 0; i < N; i++) {
				StringTokenizer stt = new StringTokenizer(br.readLine());
				int first = Integer.parseInt(stt.nextToken());
				int sec = Integer.parseInt(stt.nextToken());
				pQueue.offer(new int[] {first, sec});
			}
			
			// 1등은 무조건 합격
			int pass = 1;
			int[] first = pQueue.poll();
			int pre_grade1 = first[0];
			int pre_grade2 = first[1];
			
			for(int i = 1; i < N; i++) { // 모든 지원자 확인
				int[] grades = pQueue.poll();
				int grade1 = grades[0];
				int grade2 = grades[1];
				
				// 이전 합격자가 지금의 점수보다 등수가 둘 다 높은 경우. 불합격
				if(pre_grade1 < grade1 && pre_grade2 < grade2) continue;
				
				// 하나라도 높은 경우. 다음 지원자에 대한 지표로 삼음
				pre_grade1 = grade1;
				pre_grade2 = grade2;
				pass++;
			}
			
			System.out.println(pass);
		}
	}
}