https://www.acmicpc.net/problem/1946
문제
> 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다.
> 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다.
> 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
> 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다.
> 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
> 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.접근
어떤 사람의 두 성적이 다른 어떤 사람의 두 점수 보다 전부 뒤지면 그 사람은 떨어지게 된다.
따라서 개인의 두 성적 중 한 성적을 기준으로 오름차순으로 정렬을 한 뒤 다른 한 성적을 본다.
오름차순으로 정렬된 순위에서 1등은 다른 성적은 꼴등을 해도 상관이 없다. 따라서 일단 N명이니 N등을 초기값으로 시작해서 해당 등수와 비교한다.
그럼이제 기준값이 1등의 다른 성적으로 바뀐다.
예를 들어 1등의 다른 성적이 5등이었다면 기준값이 5등이 된다.
이제 2등인 사람은 5등 안에 들어야 탈락하지 않는다. 만약 6등이나 7등이라면 1등보다 모든 성적이 낮으므로 탈락하게 된다.
이 방식으로 기준값을 줄여나가며 해당 기준 등수 안에 든 사람의수를 센다.
문제해결
코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1946번 신입사원
static int T, N;
static Pair[] rank;
static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
while(T-->0) {
N = Integer.parseInt(br.readLine());
rank = new Pair[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
rank[i] = new Pair(Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()));
}
Arrays.sort(rank, (a,b)-> a.second - b.second);
int nR = N, cnt = 0;
for(Pair i : rank) {
if(i.first <= nR){
cnt++;
nR = i.first;
}
}
System.out.println(cnt);
}
}
public static class Pair {
int first, second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
}
후기
c++의 Pair타입을 사용하고싶어서 어떻게 하면 쓸 수 있을까 알아봤다. 마침 class 연습도 하고싶었는데 할 수 있어서 좋았다. 마치 c++을 푸는것 같아 좋았따.
