Greedy 알고리즘 방식으로 한 기준에 대해서 오름차순으로 정렬하고 다른 기준에 대해서 비교하는 방식으로 접근했다.
서류점수(paper), 면접 점수(interview)를 가지는 Worker 클래스를 생성하고 이 클래스는 정렬시 paper에 대해서 오름차순으로 정렬한다.
static class Worker implements Comparable<Worker>{ int paper; int interview; public Worker(int paper, int interview){ this.paper = paper; this.interview =interview; } public int compareTo(Worker o){ return paper-o.paper; } public String toString(){ return "서류 : "+paper +" :: 인터뷰 : "+interview+"\n"; } }
서류에 대해서 오름차순이 되었다.
서류1등은 적어도 한가지에 대해서는 다른 면접자들에서 앞서므로 패스한다.
이 서류1등의 면접 점수를 maxscore로 하여
다른 면접자들과 비교하여 이 maxscore보다 큰 면접자는, 모든 부분에서 다른 면접자보다 떨어지게되니 탈락시키며
다른 면접자가 면접 점수를 더 잘받은 경우 그 때마다 면접점수를 변경한다.
int maxscore = workerList.get(0).interview;
for(int j=1; j<n; j++) {
if (workerList.get(j).interview > maxscore) {
answer--;
}else{
maxscore = workerList.get(j).interview;
}
}
import java.util.*;
public class Main {
static class Worker implements Comparable<Worker>{
int paper;
int interview;
public Worker(int paper, int interview){
this.paper = paper;
this.interview =interview;
}
public int compareTo(Worker o){
return paper-o.paper;
}
public String toString(){
return "서류 : "+paper +" :: 인터뷰 : "+interview+"\n";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for(int i=0; i<num; i++){
int n = sc.nextInt();
List<Worker> workerList = new ArrayList<>();
int answer = n;
for(int j=0; j<n; j++){
workerList.add(new Worker(sc.nextInt(), sc.nextInt()));
}
Collections.sort(workerList);
//System.out.println(workerList.toString());
int maxscore = workerList.get(0).interview;
for(int j=1; j<n; j++) {
if (workerList.get(j).interview > maxscore) {
answer--;
}else{
maxscore = workerList.get(j).interview;
}
}
System.out.println(answer);
}
}
}