[백준_1946번] 신입사원

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

[문제]

 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1946 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			int n=sc.nextInt();
			int[] people=new int[n+1];
			
			/*
			 * 서류 점수의 순위를 인덱스로하고,
			 * 면접 점수의 순위를 해당 인덱스의 값으로 저장한다.
			 */
			for(int i=0;i<n;i++) {
				int document=sc.nextInt();
				int interview=sc.nextInt();
				
				people[document]=interview;
			}
			
			int count=1; // 면접 1등은 입사가 확실하기 때문에 count는 1로 초기화
			
			/*
			 * 1등부터 시작하는 서류 순위를 인덱스로 저장했기 때문에
			 * 배열의 인덱스 1부터 n까지 값이 저장되어 있다.
			 * 
			 * people 배열은 인덱스 1부터 n까지 서류 순위대로 정렬되어 있다.
			 * 서류 순위가 x(배열 인덱스)인 사람은 
			 * 자신보다 순위가 하나 높은 사람보다 면접 순위(배열 값)가 낮다면 입사할 수 없다. 
			 * 따라서 자신보다 순위가 한 단계 높은 사람과 배열의 값을 비교하여 
			 * 배열의 값이 작다면 입사 가능하고, 아니라면 입사할 수 없다.
			 */
			int prev=people[1];
			for(int i=2;i<=n;i++) {
				if(people[i]<prev) {
					count++;
					prev=people[i];
				}
			}
			System.out.println(count);
		}
	}
}

 

[고찰]

 이번 문제를 시간초과로 인해 2중 for문을 사용하면 안된다. 어떻게 다른 방식으로 해결할 수 있을까 고민을 해봤지만 해결방법이 떠오르지 않아 다른 사람의 코드를 참고했다. 

 처음에는 2차원 배열에 서류 등수와, 면접 등수를 저장하고, Comparator를 사용하여 서류 등수를 기준으로 정렬후 자신보다 서류 등수가 한 단계 높은 사람과 면접 등수를 비교하는 방식으로 해결했는데 이렇게 하여도 시간초과가 났다. 그래서 좀 더 검색을 해보다 참고한 아이디어는 서류 등수를 인덱스로 하는 배열에 면접 등수를 배열 값으로 저장하는 방법이었다. 그러면 Comparator를 사용하여 정렬할 필요가 없이 배열의 인덱스 1~n까지로 이미 정렬이 되어있기 때문에 이런 방법을 사용하여 시간초과 없이 정답 처리를 받을 수 있었다.

 또한 입사가 가능한 사람을 판별하는 방식은 자신 이외의 모든 사람을 검사하는 것이 아닌 자신보다 서류 등수가 하나 높은 사람보다 면접 등수도 낮게 되면 입사할 수 없게 된다. 따라서 자신보다 이전 인덱스의 사람과 면접 등수만 비교하는 방식으로 해결할 수 있는데 이렇게 되면 2중 for문이 아닌 하나의 for문으로 해결 가능하다.