[BOJ][Java] 1946. 신입 사원

문제

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

 

문제 이해

• 지원자마다 서류 등수, 면접 등수가 주어진다.
• 한 지원자 A가 다른 지원자 B보다 서류/면접 모두에서 등수가 낮으면 탈락한다.
• 최종적으로 선발될 수 있는 지원자 수의 최댓값을 구한다.

 

문제 풀이

아이디어

서류가 더 좋은 지원자를 앞에서부터 보는데, 지금까지 본 사람들 중 면접도 더 좋지 않으면
(= 기존 최솟값보다 작지 않으면), 앞선 누군가에게 둘 다 밀리게 되므로 탈락 처리된다.

구현

• 서류 등수를 기준으로 오름차순으로 정렬한다.
  • arr[서류 등수] = 면접 등수 형태로 저장한다.
• 앞에서부터 훑으며, 현재까지의 면접 등수 최솟값을 갱신하는 지원자만 카운트한다.
  • 맨 처음(서류 1등)은 무조건 선발한다.(ans = 1, minRank = arr[1])
  • i = 2..N까지 진행하며 arr[i] < minRank 체크

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= t; tc++) {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n + 1];

			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int idx = Integer.parseInt(st.nextToken());
				arr[idx] = Integer.parseInt(st.nextToken());
			}

			int ans = 1;
			int minRank = arr[1];
			for (int i = 2; i <= n; i++) {
				if (minRank > arr[i]) {
					ans++;
					minRank = arr[i];
				}
			}

			sb.append(ans).append("\n");
		}

		System.out.println(sb);
	}
}