반응형
문제
설명
처음에는 이해가 안 갔다.
하지만 생각해보면 쉬운 문제.
먼저 서류 등수를 기준으로 오름차순 정렬을 한다.
정렬을 해놓으면 이중 for문을 쓰는 등의 일일이 찾는 일 없이, for문 하나로 순차적으로 파악이 가능해진다.
(정렬 안 하고 이중 for문이라도 쓰는 순간 시간 초과남!!)
서류 1등은 다른 지원자들과 비교 안 해도 됨.
서류 2등부터 면접 등수만 가지고 다른 지원자보다 떨어지나 안 떨어지나 판단함.
처음은 1등의 면접 등수를 최소로 놓고 시작.
2등의 면접 등수가 최소 면접 등수(현재는 1등의 면접 점수) 보다 작다면 합격
최소 면접 등수는 2등의 점수로 갱신
위 과정을 마지막 지원자까지 반복하면 합격할 수 있는 최대 인원을 구하게 됨!
전체 코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Grade implements Comparable<Grade> {
int a;
int b;
Grade(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public int compareTo(Grade o) {
if(this.a > o.a) {
return 1;
} else {
return -1;
}
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int t = 0; t < T; t++) {
int N = sc.nextInt();
ArrayList<Grade> list = new ArrayList<>();
for(int i = 0; i < N; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
list.add(new Grade(a, b));
}
Collections.sort(list); // 서류 점수 기준 오름차순 정렬
int ans = 1; // 서류 1등은 무조건 통과
int min = list.get(0).b; // 면접 점수 최소값
for(int i = 1; i < N; i++) { // 서류 2등부터 시작
if(list.get(i).b < min) { // 이전의 최소 면접 점수보다 낮으면 통과
ans++;
min = list.get(i).b; // 최소 점수 갱신
}
}
System.out.println(ans);
}
}
}
GITHUB
반응형
'알고리즘 문제 > 백준' 카테고리의 다른 글
[백준 - Java] 3190번 : 뱀 (삼성 SW 역량 테스트 기출 문제) (0) | 2021.02.09 |
---|---|
[백준 - Java] 1931번 : 회의실 배정 (0) | 2021.01.25 |
[백준 - Java] 1389번 : 케빈 베이컨의 6단계 법칙 (0) | 2021.01.23 |
[백준 - Java] 16234번 : 인구 이동 (0) | 2021.01.20 |
[백준 - Java] 5567번 : 결혼식 (0) | 2021.01.19 |
댓글