BOJ01946 신입 사원

https://www.acmicpc.net/problem/1946 (opens new window)

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

Employee.java

지원자의 정보를 관리하기 위한 Employee 클래스이다.

private static class Employee {
    private final int a; // 1차 서류심사
    private final int b; // 2차 면접시험

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

    public int getA() {
        return a;
    }

    public int getB() {
        return b;
    }
}

제출 코드

우선 지원자의 데이터를 모두 입력 받아 리스트에 저장한다.

int employeeCount = scanner.nextInt();

    List<Employee> employees = new ArrayList<>();
    for (int i = 0; i < employeeCount; i++) {
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        employees.add(new Employee(a, b));
    }

각 종목 별 등수는 중복되지 않는다. 우선 서류심사를 기준으로 오름차순 정렬한다.

employees.sort(Comparator.comparingInt(employee -> employee.a));

정렬이 완료되면 서류심사를 기준으로 1등 부터 정렬된 것을 확인할 수 있다. 즉 이제 부터 면접시험의 등수가 곧 기준이 된다. 서류심사는 이미 정렬되어 있기 때문에 위에서 부터 탐색하며 면접시험의 등수가 더 낮은 사람이 발견되면 그 사람은 합격함을 나타낸다.

합격이 판단되면 이제 그 사람이 합격의 기준이 된다.

int count = 1;
Employee standard = employees.get(0);
for (int i = 1; i < employeeCount; i++) {
    if (standard.b > employees.get(i).b) {
        count++;
        standard = employees.get(i);
    }
}

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class BOJ1946 {

    private static class Employee {
        private final int a; // 1차 서류심사
        private final int b; // 2차 면접시험

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

        public int getA() {
            return a;
        }

        public int getB() {
            return b;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();

        while (t-- > 0) {
            int employeeCount = scanner.nextInt();

            List<Employee> employees = new ArrayList<>();
            for (int i = 0; i < employeeCount; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();

                employees.add(new Employee(a, b));
            }

            employees.sort(Comparator.comparingInt(employee -> employee.a));

            int count = 1;
            Employee standard = employees.get(0);
            for (int i = 1; i < employeeCount; i++) {
                if (standard.b > employees.get(i).b) {
                    count++;
                    standard = employees.get(i);
                }
            }

            System.out.println(count);
        }
    }
}

#algorithm #BOJ #그리디 알고리즘 #정렬