[백준 - Java] 1946번 : 신입 사원

문제

www.acmicpc.net/problem/1946

1946번: 신입 사원

설명

처음에는 이해가 안 갔다.

하지만 생각해보면 쉬운 문제.

 

먼저 서류 등수를 기준으로 오름차순 정렬을 한다.

정렬을 해놓으면 이중 for문을 쓰는 등의 일일이 찾는 일 없이, for문 하나로 순차적으로 파악이 가능해진다.

(정렬 안 하고 이중 for문이라도 쓰는 순간 시간 초과남!!)

 

서류 1등은 다른 지원자들과 비교 안 해도 됨.

서류  2등부터 면접 등수만 가지고 다른 지원자보다 떨어지나 안 떨어지나 판단함.

 

처음은 1등의 면접 등수를 최소로 놓고 시작.

2등의 면접 등수가 최소 면접 등수(현재는 1등의 면접 점수) 보다 작다면 합격

최소 면접 등수는 2등의 점수로 갱신

 

위 과정을 마지막 지원자까지 반복하면 합격할 수 있는 최대 인원을 구하게 됨!

전체 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Grade implements Comparable<Grade> {
	int a;
	int b;

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

	@Override
	public int compareTo(Grade o) {
		if(this.a > o.a) {
			return 1;
		} else {
			return -1;
		}
	}
}

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for(int t = 0; t < T; t++) {
			int N = sc.nextInt();
			ArrayList<Grade> list = new ArrayList<>();

			for(int i = 0; i < N; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();

				list.add(new Grade(a, b));
			}

			Collections.sort(list); // 서류 점수 기준 오름차순 정렬 

			int ans = 1; // 서류 1등은 무조건 통과 
			int min = list.get(0).b; // 면접 점수 최소값 
			for(int i = 1; i < N; i++) { // 서류 2등부터 시작 
				if(list.get(i).b < min) { // 이전의 최소 면접 점수보다 낮으면 통과 
					ans++;
					min = list.get(i).b; // 최소 점수 갱신 
				}
			}
			System.out.println(ans);
		}	
	}
}

GITHUB

KwonMinha/BOJ