아래는 문제 링크입니다.
https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성
www.acmicpc.net
문제 설명은 아래와 같다.
문제 해결 과정
처음에 3중 for문으로 해결하려고 했다가 시간 초과... 이후 한동안 바로 해결책이 떠오르지 않아 방치해두었다.
그러다가 Comparable를 이용한 객체의 정렬을 배웠다. 아래 포스팅에서 학습한 내용을 확인할 수 있다.
https://devdebin.tistory.com/79?category=1004568
좌표정렬
오늘 이렇게 오랜만에 알고리즘 게시글을 남기는 이유는 중요한 것을 배워서 기록하기 위함이다. 바로 객체 정렬을 위해 Comparable 인터페이스를 사용했기 때문이다. 좌표 정렬에 관한 문제다. 설
devdebin.tistory.com
그래서 일단 서류 시험(x)을 기준으로 먼저 정렬하자는 아이디어를 사용했다.
이렇게 정렬을 하면 1차적으로 서류 시험 성적을 바탕으로 객체들이 정렬된다.
이제 다음의 아이디어가 중요하다. 이걸 떠올리는데 오래걸렸다.. 어떻게 하면 for문을 한 번 더 안돌릴까?!
먼저 서류 시험 1등의 면접 등수를 기준으로 둔다.(standard)
그리고 합격자 등수를 알려주는 count 변수에는 서류 시험 1등 합격자는 어짜피 합격이므로 값을 1로 할당한다.
이제 서류 시험 등수를 기준으로 for문을 돌린다.
그러면 1등을 제외하고 2등부터 시작하는데 2등은 1등의 면접 등수보다 높으면 합격한다.
우리는 1등의 면접 등수를 standard라는 변수에 넣어놓았다.
이제 서류 시험 2등이 1등보다 면접 등수가 높아서 합격했다고 가정을해보자.
그러면 서류 시험 3등은 언제 합격할까? 서류 시험 2등보다 면접 등수가 높아야할 것이다.
그러면 여기서 중요한 부분이 나온다. 서류 시험 3등은 서류 시험 1등의 면접 등수를 고려해야하는가?
전혀 그럴 필요가 없다. 왜냐면 서류 시험 2등의 면접 등수가 서류 시험 1등보다 높으므로,
서류 시험 2등의 면접 등수만 고려하면 된다.
왜냐하면 제일 면접 등수가 높은 것이 서류 시험 2등의 면접 등수이기 때문이다.
서류 시험 3등이 서류 시험 2등보다 면접 시험 등수가 높으면 무조건 합격하고,
서류 시험 3등이 서류 시험 2등보다 면접 시험 등수가 낮으면 무조건 탈락하기 때문이다.
이건 우리가 서류 시험 정렬을 통해 가능한 얘기다.
이러면 자신보다 서류 등수가 높은 사람을 제치고 합격한 이들의 면접 등수를 넣을 변수가 필요한데, (이전 예시에서는 2등의 면접 등수) 이게 앞에서 언급한 standard 변수다. 탈락한 사람들의 면접 시험 등수는 신경 쓸 필요가 없다.
이 standard 변수를 가지고 비교해나가면서 count를 올리고, 합격자가 발생하면 standard 변수에 그들의 면접 등수를 넣어주면 된다. 이런 논리로 문제를 해결할 수 있다.
예시
| 서류 등수 | 면접 등수 |
| 1 | 4 |
| 2 | 3 |
| 3 | 2 |
표 아래에 인원이 더 있지만 신경쓰지말자.
서류 1등은 당연히 통과다. 왜냐면 서류 등수에서 자신보다 높은 사람이 없으므로 비교할 경우의 수가 없기 때문이다.
서류 2등을 생각해보자. 서류 2등은 서류 1등과 비교해야 한다. 여기서 면접 등수가 밀리면 탈락이다. 그러나 밀리지 않으므로 통과다. 서류 3등은 어떨까 1등 2등을 신경써야할까? 서류 3등은 이미 1등과 2등 에게 밀렸다. 그런데 2등이 남아있다는 것은 1등보다 서류 면접이 높았기 때문이다. 그러면 서류 3등은 앞에 있는 인원들의 모든 면접 등수보다 서류 3등의 면접 등수가 높아야 한다. 앞에서는 서류 1등의 면접 등수를 제치고 합격한 서류 2등이 최고 면접 등수다. 이와 비교해서 서류 3등의 면접 등수가 높다면 합격인 것이다.
즉 서류 등수로 정렬한 앞 사람들의 최고 면접 등수보다 본인이 높으면 합격하는 것이다. 그럼 이제 합격한 사람의 등수가 최고 면접 등수가 되어서 비교에 사용되는 것이다.
해결 코드
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
class Test implements Comparable<Test>{
public int x;
public int y;
public Test(int x, int y){
this.x = x; //서류 등수
this.y = y; //면접 등수
}
@Override
public int compareTo(Test o){
if(this.x > o.x ) return 1; //앞선 사람이 서류 등수가 낮다면 교체
return -1; //앞선 사람이 서류 등수가 높다면 그대로
}
}
public class Review{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int num = Integer.parseInt(br.readLine());
for(int i=0; i< num;i++){
int total = Integer.parseInt(br.readLine());
ArrayList<Test> arr = new ArrayList<>();
for(int j=0;j<total;j++){
String[] str = br.readLine().split(" ");
arr.add(new Test(Integer.parseInt(str[0]),Integer.parseInt(str[1])));
}
Collections.sort(arr); //서류 심사 등수로 정렬
int standard = arr.get(0).y; //서류 심사 1등 면접 등수를 기준으로 둔다.
int count=1; //서류 심사 1등을 포함해서 시작하므로 1.
for(int z=1;z<total;z++){
if(standard>arr.get(z).y){ //현재 사람(z)이 앞에 서류 점수가 높은 사람보다 면접 등수가 높다면
count++; //count를 올리고
standard= arr.get(z).y; //기준을 현재 사람의 면접 등수로 바꾼다
}
}
bw.write(count+"\n");
}
bw.flush();
}
}
이상으로 포스팅을 마칩니다. 감사합니다.
댓글