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

• 문제 조건: 채용되기 위해서는 서류 심사 성적과 면접 심사 성적 둘 중 하나는 다른 어떤 사원보다 높아야 한다.

= 서류 심사 성적과 면접 심사 성적이 둘 다 낮은 신입 사원이 한 명이라도 존재하면 신입사원으로 채용될 수 없다

• 문제 해결 과정:

  1) 하나하나 모두 비교하면 O(N^2) -> 10000000000 이기 때문에 제한 시간을 넘어간다.

  2) 한 명의 지원자를 대상으로 채용여부를 검사할 때, 그 사원의 서류 점수보다 높은 지원자들과의 면접 점수만 비교하면 된다.

• Key

  1) 서류 심사 등수 순으로 정렬한다(반대의 경우도 가능)

  2) 면접 등수는 서류 심사 등수가 현재 검사하는 지원자보다 높은 지원자들 중 가장 높은 등수랑만 비교하면 된다. 즉, 반복문을 돌면서 max값을 업데이트 하면 O(1) 로 비교 가능하다.

• 시간복잡도: O(nlog n) -> Collections.sort

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		StringTokenizer str;
		for(int i=0; i<T; i++) {
			int count=Integer.parseInt(br.readLine());
			int[] paper=new int[count];
			int[] interview=new int[count];
			
			ArrayList<Applicant> list=new ArrayList<>();

			for(int j=0; j<count; j++) {
				str=new StringTokenizer(br.readLine());
				paper[j]=Integer.parseInt(str.nextToken());//서류등수
				interview[j]=Integer.parseInt(str.nextToken());//면접등수
				
				list.add(new Applicant(paper[j], interview[j]));
				
			}
			
			Collections.sort(list, new Comparator<Applicant>() {
				//서류 등수가 높은 순으로 정렬한다
				@Override
				public int compare(Applicant o1, Applicant o2) {
					return o1.paper < o2.paper ? -1 : 1;
				}
			});
			
			int ans=count; //합격자는 전체 지원자로 초기화
			int in=list.get(0).interview;//서류 1등의 면접 등수로 초기화
			for(int j=1; j<list.size(); j++) {
				//서류 등수가 높은 순 -> j 이전 데이터 중 가장 높은 면접 등수와만 비교하면 됨
				int cur=list.get(j).interview; //현재 검사하는 지원자의 면접 등수
				if(in < cur){//저장된 면접 등수보다 낮으면
					ans--;//감소
				}
				if(cur < in)//높으면
					in=cur;//max값 업데이트 
			}
			
			System.out.println(ans);
		}
	}

}

class Applicant{
	int paper;
	int interview;
	
	Applicant(int paper, int interview){
		this.paper=paper;
		this.interview=interview;
	}
}