[C언어/BOJ] BOJ 1946 신입사원

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다.

인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다.

최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

 

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다.

즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

 

문제를 한줄로 요약하면 시험 본 면접생들중에서 어떤 면접생이 다른 한명보다 서류,면접 둘다 점수가 낮다면

걔는 떨어지는것이다.

 

 

풀이

이 문제를 보고 떠오른 1차적인 풀이는 

1번 면접생부터 N번 면접생까지 각각의 면접생의 점수를 가지고

 

1번부터 ~ N번 면접생까지 점수를 비교해보는것입니다. 

하지만 이 알고리즘은  O(N*N)의 시간복잡도를 가지고 N이 최대 10^5 의 입력값이 가능하므로 시간초과가 뜹니다.

 

따라서 다른 접근이 필요합니다.

 

판단 수를 줄이기위해서 위와 같은 모습에서 서류 순위를 오름차순으로 정리한 기준으로 나타냅니다.

다음과 같이 나타납니다. 이렇게 되면 서류는 1등 밑으로 다 탈락이므로 볼 필요가 없습니다.

따라서 서류 순위 1, 면접순위 4 지원자를 최고 득점자라고 가정하고 면접 점수만 비교해서

면접 순위가 4보다 높은 면접순위를 뽑습니다. 

여기서 4와 2를 만나게되면 2는 면접순위가 지금 현재 최고 득점자인  4보다 높으므로 통과입니다.

 

여기서 최고 득점자의 면접점수를 2로 다시 바꾸어주어야합니다. 그 이유는 7,3의 경우 면접순위가 4보다 높지만 4,2에 둘다 지므로 면접순위도 더 높은 순위의 통과자가 생길때마다 바꾸어주어야합니다.

다시 진행되면서 빨간색박스 지원자가 기준점이 되고 파란색박스 지원자의 면접순위가 1이므로 2보다 높습니다.

따라서 통과입니다.

6,1 빨간색 박스 지원자가 기준점이 되고 면접순위가 1이므로 1보다 더 높은순위는 없습니다. 따라서 

1,4 / 4,2 /6,1 지원자 3명이 통과입니다. 

 

다음은 코드입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h>   typedef struct Newrecruit {     int grade;//성적     int face; //면접 }NEW; //지원자의 성적을 담은 구조체 선언 int Ishecruited(NEW* target, int num); void arrayquicksort(NEW* array, int start, int end); void printarray(NEW* target,int n); void swapstruct(NEW* A, int a, int b); int main() {     int T, N, result = 0;//테스트 개수와 지원자의 수     scanf("%d", &T);       for (int k = 0; k < T; k++) {         scanf("%d", &N);         NEW* new = malloc(sizeof(NEW) * N);         for (int i = 0; i < N; i++) {             scanf("%d %d", &new[i].grade, &new[i].face);         }//지원자의 서류와 면접점수를 입력받는다           arrayquicksort(new,0, N-1);         printarray(new,N);         result = Ishecruited(new, N);         printf("%d", result);         puts("");     }     return 0; }   int Ishecruited(NEW* target, int num) {     int a, b, cnt = 0;     int pass = 0;     int winner = 0;     winner = target[0].face;     for (int a = 1; a < num; a++) {         if (target[a].face < winner)         {             winner = target[a].face;             pass++;         }         if (winner == 1) break;     }     return pass + 1; }   void arrayquicksort(NEW* array, int start, int end) {     if (start >= end) {         return;     }     int i = start + 1;     int j = end;     int temp;     int key = start;     while (i <= j) {           while (i <= end && array[i].grade <= array[key].grade) i++;         while (j > start&& array[j].grade >= array[key].grade) j--;         if (i > j) {             swapstruct(array, j, key);         }         else {             swapstruct(array,i, j);         }       }// while문이 종료됐다는것은 엇갈렸다는 것     arrayquicksort(array, start, j - 1);     arrayquicksort(array, j + 1, end);     return 0; }   void printarray(NEW* target,int n) {         for(int i=0;i<n;i++){         printf("%d ",target[i].grade);     } } void swapstruct(NEW* A, int a, int b) {     NEW* temp = malloc(sizeof(NEW));     temp->grade = A[a].grade;     A[a].grade = A[b].grade;     A[b].grade = temp->grade;       temp->face = A[a].face;     A[a].face = A[b].face;     A[b].face = temp->face;     free(temp);     return 0; }   Colored by Color Scripter

cs