https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성
www.acmicpc.net
문제를 풀기에 앞서 일단 성적을 정렬시켜야 한다
정렬을 시켜놔야 성적을 비교하기 쉬워지기 때문이다
나는 서류 심사 성적을 기준으로 오름차순 정렬시켰다
문제의 예제에서 Test case 2의 경우를 예로 들어보자
| 서류 심사 순위 | 면접 순위 |
| 3 | 6 |
| 7 | 3 |
| 4 | 2 |
| 1 | 4 |
| 5 | 7 |
| 2 | 5 |
| 6 | 1 |
이제 서류 심사 성적을 기준으로 오름차순 정렬시켜 놓고 보자
| 서류 심사 순위 | 면접 순위 |
| 1 | 4 |
| 2 | 5 |
| 3 | 6 |
| 4 | 2 |
| 5 | 7 |
| 6 | 1 |
| 7 | 3 |
서류 심사 1등은 다른 모든 이들에게 서류 심사 점수는 이기므로 떨어질 이유가 없다
따라서 합격이다
다음으로 2등(서류 심사)을 보자
1등보다 서류 순위도 밀리는데 면접 순위도 밀린다
따라서 서류 심사 2등은 떨어진다
다음 3등을 보자
이미 떨어진 2등보다 서류 순위, 면접 순위 둘 다 밀린다
그리고 어차피 합격하려면 면접 순위가 1등의 면접 순위인 4등보다 높아야 하는데 그렇지 못한다 -------------------------------- (핵심)
3등도 불합격이다
다음, 4등을 보자
일단 3등보다는 면접 순위가 높다
2등과 1등과 비교해도 면접 순위가 높다
서류 순위 4등은 서류 1, 2, 3위보다 서류 순위는 밀리지만 면접 순위는 더 높으므로 합격이다
5등을 보자
면접 순위가 7등으로, 서류 1~4등에게 모두 면접 순위가 밀린다
합격하기 위해서는 지금까지 면접 최고 순위인 2등보다 높아야 한다 ------------------------- (핵심)
불합격...ㅠ
다음 6등을 보자
면접 순위 1등이다
서류 1~5등보다 면접 순위가 더 높으므로 합격이다
마지막으로 7등을 보자
7등이 합격하기 위해서는
방금 전 서류 6등보다 면접 점수도 높아야 한다 --------------------- (핵심)
하지만 6등의 면접 순위인 1등보다 더 높을 순 없으므로 불합격...
이를 코드로 나타내면 아래와 같다
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct _grade {
int a; // 서류 심사 성적
int b; // 면접 성적
} grade;
int compare(const void* x, const void* y) {
grade A = *(grade*)x;
grade B = *(grade*)y;
if (A.a > B.a)
return 1;
else if (A.a < B.a)
return -1;
else return 0;
}
int main() {
int T, N, cnt = 0;
scanf("%d", &T);
int i, j, k;
for (i = 0; i < T; i++) {
scanf("%d", &N);
cnt = 0; // cnt: 불합격자의 수
grade* score = (grade*)malloc(sizeof(grade) * N);
for (j = 0; j < N; j++)
scanf("%d %d", &score[j].a, &score[j].b);
qsort(score, N, sizeof(grade), compare);
int save_b = score[0].b;
for (j = 1; j < N; j++) {
for (k = j - 1; k >= 0; k--) {
if (score[j].b > save_b) {
cnt++;
break;
}
else {
save_b = score[j].b;
break;
}
}
}
printf("%d\n", N - cnt);
free(score);
}
return 0;
}
서류 성적 순위와 면접 성적 순위는 score라는 이름의 구조체에 저장해 주었다
Test case 별로 성적을 모두 입력받으면
qsort를 이용하여 서류 성적을 기준으로 오름차순 정렬시켜주었다
그리고 서류 성적 1등부터 시작해서 for 문을 이용해 자기보다 서류 점수가 더 높은 사람과 면접 점수를 비교하였다
이때 시간 절약을 위해 코드 위에서 설명할 때 (핵심)이라고 적은 파란 글씨 부분을 구현해 주었다
서류 순위 1등부터 시작해 서류 N 등까지 하나씩 면접 점수를 다른 사람과 비교하는데
이때 자기보다 더 서류 순위가 높은 사람들과 비교하므로
면접 순위가 지금까지 봐왔던 사람들의 순위보다 더 높아야 합격한다
따라서 나는 '지금까지 봐왔던 사람들 중 면접 최고 성적'을 save_b라는 이름의 변수로 저장해두고
save_b보다 성적이 더 좋으면 합격하고 더 낮으면 바로 불합격시키는 방식으로 만들었다 -------------------------- (이게 핵심)
처음엔 바로 불합격시키지 않고 자기보다 더 높은 서류 성적인 사람들의 모든 면접 순위를 비교하는 방식으로
시간 복잡도가 O(n^2)인 코드를 만들었는데
시간 초과로 오답이 났다
그래서 지금까지의 최고 면접 점수보다 더 낮으면 바로 불합격시키도록 break를 걸어주었고 덕분에 시간이 절약되고 정답 처리를 받았다
난이도: solved.ac 실버 1