문제
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다.
각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다.
두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
출력
각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.
🧐 문제 이해하기
문제를 몇 번봐도 이해가 가질 않았다..
나름 꼼꼼히 읽었다고 생각했는데도 순위가 아니라 점수로 이해해 테스트 케이스의 정답마저 이해가 안갔었다 ..^^
다른 블로그를 검색해보고 스터디 팀원의 설명을 듣고 나서야 이해가 갔다🥲 (짱입니다..)
- 서류점수나 면접점수 둘 중 하나를 놓고 정렬
- 문제에서 어떤 A의 성적이 다른 지원자에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다고 했다-> 이 말은 다른 지원자들의 점수를 비교했을때 1등은 사람들은 일단 무조건 통과라는 말이다.
- 서류 점수를 기준으로 정렬했다고 생각해보자
- 위 표에서 서류 1등은 무조건 통과다.
- 서류 2등이 통과하기 위해서는 서류1등인 면접 점수를 이겨야한다.
(서류등수에서 1등을 제외하고는 다른 등수보다 높기 때문에 다른 등수들하고는 비교할 필요가 없다.) ->
서류 2등의 면접 등수가 서류 1등의 면접 등수보다 더 높기 때문에 통과! - 서류 2등이 통과했으니 기준점은 서류2등의 면접 등수인 3등이 되었다.
- 서류 3등의 면접등수가 서류2등보다 더 높으므로 합격!, 기준점은 면접등수 2등으로 바뀌었다.
- 서류 4등의 면접등수는 1등으로 기준점보다 높기 때문에 합격,
- 서류 5등은 기준점보다 낮기때문에 불합격
🫥 메모리 부족 코드 ^_^
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class No_1946 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T =sc.nextInt();
for(int i=0;i<T;i++){
int N=sc.nextInt();
int S[][]=new int[N][N];
for(int j=0; j<N; j++){
S[j][0]=sc.nextInt();//성적
S[j][1]=sc.nextInt();//면접
}
Arrays.sort(S, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]) {
return o1[1] - o2[1];
}else {
return o1[0] - o2[0];
}
}
}); // 성적을 기준으로 정렬
int count =1;
int base=S[0][1];
for(int j=1;j<N;j++){
if(base>S[j][1]){
count++;
base=S[j][1];
}
}
System.out.println(count);
}
}
}
맞는 풀이이긴 하지만 메모리 초과로 불합격했다
코드 자체는 맞는데 정말 어렵다 어려워 ~^^..
Arraylist로 바꿔서 해도 통과이긴하지만 검색하다가 증맬 신박한 방법을 발견했다.(출처)
다른 문제풀이 💡
- 등수는 겹치지 않는다고 했으므로 배열의 인덱스를 서류 점수로 받고, 인덱스 안에 면접 점수를 받는 입력받는 방식이다.
- 이렇게 하면 따로 정렬할 필요없이 그대로 사용하면 된다..
- 증맬 이세상엔 천재가 너무 많다..
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class No_1946 {
public static void main(String[]args){
Scanner scan = new Scanner(System.in);
int T= scan.nextInt();
for(int i=0;i<T;i++){
int N=scan.nextInt();
int count=1;
int work[]=new int[N+1];
for(int j=0;j<N;j++){
int a=scan.nextInt();
int b=scan.nextInt();
work[a]=b;
}
int base= work[1];
for(int j=2;j<=m;j++){
if(work[j]<base){
base=work[j];
count++;
}
}
System.out.println(count);
}
scan.close();
}
}
배열로 하면 [0]의 공간이 비어있긴 하지만 이 부분은 배열의 크기를 m으로 하고,
int a= scan.nextInt-1로 하면 될 것 같다
마무리 🧐
정말 쉽지 않았던 문제였다.
차라리 문제 해결 방법이 생각이 안나는건 그렇다 치는데 문제조차 이해가 안갈때는 더 별로다
메모리초과 대처를 위해 시간복잡도도 생각 많이 공부해봐야겠다.
어려운 알고리즈므음
