[백준 1946번] 신입사원 (JAVA)

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

1946번: 신입 사원

 

 

문제

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

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

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

 

 

입력

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

 

 

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

 

 

풀이

우선, 신입사원들의 번호와 순위를 함께 가져가기 위해 Emp라는 Class를 생성한 뒤, 1) 신입사원의 번호와 2) 서류심사 순위, 3) 면접 성적의 순위를 저장했다.

그 후 서류와 면접 중 하나를 기준으로 오름차순 정렬을 통해 비교해나가면 된다. (아래 코드와 설명은 서류를 기준으로 정렬)

 

처음에는 1등은 2,3,4,5등과 비교, 2등 3,4,5등과 비교 이런 식으로 전부 다 비교하면서 중간에 가지치기를 해서 시도해봤는데 100,000*100,000 = 10,000,000,000 (100억) 이어서 아니나 다를까 당연한 시간 초과였다.

그래서 이중 for문으로 돌았던 것을 줄였다.

 

서류심사의 순위가 낮은 사원들은 앞 순위의 사원들보다 무조건 면접의 순위가 더 높아야 한다. 즉, 신입사원 리스트를 정렬한 후 순서대로 돌 때 현재 사원의 면접 순위보다 높은 사원이 이미 존재했으면 안 된다.

서류 심사가 나 자신(현재 체크하고 있는 사원)보다 순위가 높은 사원들은 면접 순위는 전부 나보다 낮아야 내가 뽑힐 수 있다.

이를 전제로 탐색을 해나가면 된다.

서류 심사를 1등부터 마지막까지 돌아보면서 면접 심사의 기준을 최솟값으로 갱신해나간다. 문제에 같은 등수는 없다고 했으니 동일한 값은 계산하지 않아 줘도 된다.

 

예제를 설명한대로 그림을 그려보면 좀 더 이해가 쉬울 것 같다.

그림을 보면 뽑힐 수 있는 사원들은 면접 순위가 최솟값으로 계속해서 갱신되는 것을 볼 수가 있다.

 

그리고 주의할 점!!

서류에서 1등인 사원은 면접 순위가 1등부터 꼴등까지 전부 가능하기 때문에 무조건 뽑힐 수 있어서 경우의 수에 포함하여야 한다.

 

 

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Baekjoon1946_신입사원 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		boolean[] employee;
		ArrayList<Emp> list;
		for(int t=0; t<T; t++) {
			int N = Integer.parseInt(br.readLine());

			employee = new boolean[N+1];
			list = new ArrayList<>();
			for(int n=1; n<=N; n++) {
				StringTokenizer st = new StringTokenizer(br.readLine()," ");

				int document = Integer.parseInt(st.nextToken());
				int interview = Integer.parseInt(st.nextToken());

				list.add(new Emp(n, document, interview));
			}
			Collections.sort(list); //서류 순서대로 정렬
            
			int tot = 1;
			int min = list.get(0).intRank;
			for(int i=1; i<N; i++) {
				if(list.get(i).intRank < min) {
					min = list.get(i).intRank;
					tot++;
				}
			}
			sb.append(tot+"\n");
		}
		System.out.println(sb.toString());
	}
	static class Emp implements Comparable<Emp>{
		int num; //사원번호
		int docRank; //서류 랭크
		int intRank; //면접 랭크
		public Emp(int num, int docRank, int intRank) {
			this.num = num;
			this.docRank = docRank;
			this.intRank = intRank;
		}
		@Override
		public int compareTo(Emp o) {
			return this.docRank - o.docRank;
		}


	}
}

 

 

 

 

 

---