문제
문제 및 예제 해설
시험성적 A,B 가 있을 때 성적 중 하나가 다른 지원자보다 떨어지지 않는다면 합격한다.
-> 즉, 두 개의 성적 중 1등이 있다면 무조건 합격이며
A(또는 B)성적이 n등인 X지원자가 합격하기 위해서는 A시험의 1,2,..n-1 등 지원자들보다 B성적이 높아야 한다. 만약 한 명이라도 X지원자보다 B 성적이 높다면 X지원자가 A,B 두 항목에서 모두 뛰어나다고 할 수 없기 때문에 탈락이다.
ex1) 1번 지원자가 A:1등, B:2등 이고 2번 지원자가 A:2등, B:1등
의 경우에는 1번 지원자는 A 시험 성적이 2번 지원자보다 뛰어나고, 2번 지원자는 B 시험 성적이 1번 지원자보다 뛰어나기 때문에 2명이 합격하게 된다.
ex2) 예제의 첫번째 케이스 (순서대로 1,2,3,4,5 지원자라고 가정)
3 2
1 4
4 1
2 3
5 5
1번 지원자 : A시험에서 3등, B시험에서 2등을 했다.
1번 지원자보다 A시험을 잘본 2번 지원자(A시험 1등) 은 B시험에서 4등을, 4번 지원자(A시험 2등)는 3등을 했으므로 1번 지원자는 합격이다.
2번 지원자 : A시험에서 1등을 했으므로 다른 지원자들보다 A 성적이 뛰어나기 때문에 합격
3번 지원자 : A시험에서 4등이지만 B시험에서 1등으로 다른 지원자들보다 B 성적이 뛰어나기 때문에 합격
4번 지원자 : A시험에서 2등이나 B시험에서 A시험의 1등인 2번 지원자의 B시험 성적(4등) 보다 뛰어나므로 합격
5번 지원자 : 모든 시험에서 꼴등이므로 탈락
풀이방법
- 지원자 수만큼의 배열을 만들고 배열의 인덱스를 첫번째 시험 등수로, 배열의 안에는 두번째 시험 등수를 넣는다.
// first: 첫번째 시험성적, sec: 두번째 시험성적
ranking[first] = sec;- 배열의 인덱스는 첫번째 시험의 등수이므로 인덱스가 커질수록 첫번째 시험의 등수가 커진다.
첫번째 시험을 N등한 사람이 합격하기 위해서는 첫번째 시험의 등수가 1~N-1등인 사람들보다 두번째 시험등수가 높아야한다.
따라서 배열의 인덱스를 2부터 시작하여(1등은 무조건 합격) +1 씩 하여 N번째 인덱스 값이 배열의 2~N-1 안에 저장된 값보다 작은지 비교하여 작다면 합격(answer++)자 수를 늘린다.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception {
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
int num = Integer.parseInt(br.readLine());
solution(num);
}
}
public static void solution(int num) throws Exception {
if (num == 1) {
System.out.println(1);
return;
}
int[] ranking = new int[num + 1];
int answer = 1;// 첫번째 시험 1등
for (int i = 1; i <=num; i++) {
String[] str = br.readLine().split(" ");
int first = Integer.parseInt(str[0]);
int sec = Integer.parseInt(str[1]);
ranking[first] = sec;
}
loop:for (int i = 2; i <= num; i++) {
int score = ranking[i];
// 첫번째 시험 3 4 두번째 시험 2 1
if(score == 1) {
answer ++;
continue;
}
for(int j=i-1; j>0; j--) {
if(ranking[j] < score) continue loop;
}
answer ++;
}
System.out.println(answer);
}
}