1946번 신입사원

백준 온라인 저지 1946번 신입사원

---

문제 출처 : https://www.acmicpc.net/problem/1946

풀이과정

이 문제는 지원자의 서류심사 성적과 면접 시험 성적 중 적어도 하나는 다른 "모든" 지원자보다 떨어지지 않는 사람만 선발해야 합니다.

둘 중 하나의 성적이 1등인 사람은 무조건 선발이 되야합니다. 그렇기 때문에 둘 중 하나를 기준으로 정렬하고 다른 성적 등수만 비교하면 간단해 집니다.

예시

사이트에 있는 입력를 통해 서류심사 성적 순위를 오름차순으로 정렬한 예시입니다.

서류심사 성적이 오름차순으로 정렬되어 있기 때문에 우리는 자격이 있는지 검사할 때 서류심사 성적은 신경쓰지 않아도 됩니다. 1등을 제외한 모든 사람은 1등보다 성적이 떨어지므로 면접심사 성적에서 우위를 가져야 선발될 수 있죠. 그렇기 때문에 면접심사 성적을 검사해야 합니다.

형광색으로 칠해진 부분은 현재 위치와 비교해야할 값들을 의미합니다.

우선 서류가 1등인 사람은 제외시켜야 합니다. 그 이유는 서류 성적이 다른 모든 지원자보다 떨어지지 않기 때문입니다.

그러므로 서류가 2등인 사람부터 봐보겠습니다. 서류가 2등인 사람의 면접 성적은 서류가 1등인 사람의 면접 성적보다 낮습니다. 적어도 하나는 다른 지원자들보다 떨어지지 않아야하는데 둘 다 떨어지므로 서류가 2등인 사람은 선발될 수 없습니다.

서류가 6등인 사람을 봐보겠습니다. 서류가 6등인 사람은 자신보다 서류성적을 잘 받은 사람들보다 면접성적이 좋으므로 선발될 수 있습니다. 이 과정을 마지막까지 반복하면 선발될 수 있는 인원수를 최종적으로 파악할 수 있습니다. 

현재 위치를 기준으로 앞에 있는 성적들을 다 비교하면 O(N^2)가 나올 수 있습니다. 그렇기 때문에 다 비교하는게 아니라 제일 높은 면접등수를 가지고있던 (서류 4등, 면접 2등인 지원자) 사람하고만 비교하면 O(N)으로 문제를 해결할 수 있습니다. 그러므로 가장 높은 면접등수를 저장하고있는 변수가 필요하겠죠?

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(in.readLine());
		while (testCase-- > 0) {
			int n = Integer.parseInt(in.readLine());
			Person[] person = new Person[n];
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				person[i] = new Person(a, b);
			}
			Arrays.sort(person);
			int ans = 1;
			int min = person[0].b;

			for (int i = 1; i < n; i++) {
				if (person[i].b <= min) {
					min = person[i].b;
					ans++;
				}		
			}
			System.out.println(ans);
		}

	}
}

class Person implements Comparable <person> {
	int a;
	int b;

	Person(int a, int b) {
		this.a = a;
		this.b = b;
	}

	@Override
	public int compareTo(Person o) {
		// TODO Auto-generated method stub
		return this.a - o.a;
	}
}

위 코드는 O(nlogn + n) 이므로 복잡도는 O(nlogn)이 됩니다.

위에 코드를 제출했을때 AC를 받긴했으나 1.5초가 걸린것을 보고 좀더 빠른 방법이 있을거라는 생각이 들었습니다.

고민해본 결과 입력을 받을 때 동석차가 없다고 했으므로 그냥 1차원 배열을 선언하고 , 서류심사 성적을 인덱스로해서 그 인덱스에 해당하 는 배열에 면접성적의 등수를 입력하면 정렬을 따로 할 필요가 없어집니다. 그래서 복잡도를 O(n)으로 줄일 수 있었고 500ms로 수행속도를 3배 줄일 수 있었습니다. 

개선된 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(in.readLine());
		while (testCase-- > 0) {
			int n = Integer.parseInt(in.readLine());
			int arr[] = new int[n+1];
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr[a] = b;
			}
		
			int ans =1;
			int min = arr[1];
			for(int i=2; i<=n;i++) {
				if(arr[i] <= min) {
					ans++;
					min = arr[i];
				}
			}
			System.out.println(ans);
		}

	}
}