[백준] 1946번 - 신입사원 (Java)(○)

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

1946번: 신입 사원

 

[문제접근]

입력값이 점수가 아니라 순위라는 것을 이해하지 못해서 한참을 헤맸다.
먼저 직원을 선발하지 않는 조건을 잘 살펴보자.

* 선발하지 않는 조건
1. 서류순위와 면접순위가 더 높은 지원자가 있다면 그 지원자는 떨어진다.
2. 서류순위를 기준으로 오름차순 정렬을 하면, 자기보다 서류순위가 떨어지는 사람들은 비교할 필요가 없다.
3. 나보다 서류순위가 높음 지원자의 면접순위와 내 면접순위를 비교해서 내 면졉순위가 높으면 붙고, 낮으면 떨어진다.
4. 내가 붙으면 나의 면접순위가 비교하는 기준이 된다.

 

[문제풀이]

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

class Employee implements Comparable<Employee> {
    int paper;
    int interview;

    Employee (int paper, int interview) {
        this.paper = paper;
        this.interview = interview;
    }

    @Override
    public int compareTo(Employee o) {
        // 서류순위를 기준으로 오름차순 정렬
        return this.paper - o.paper;
    }
}

public class Main {
    static int T, N;
    static ArrayList<Employee> list;

    void Solve() {
        int ans = 1; // 서류1등은 일단 무조건 합격임
        int pivot = list.get(0).interview; //서류 1등의 면접점수를 기준점으로 삼음
        for (int i=1; i<N; i++) { // 서류 2등부터 비교 시작
            if (list.get(i).interview < pivot) {
                // 현재 지원자의 면접 순위가 앞의 수위보다 높다면 합격
                ans++; // 합격자수 증가
                pivot = list.get(i).interview; // 기준을 현재 인터뷰 순위로 교체
            }
        }
        System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        for (int i=0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            list = new ArrayList<>();
            for (int j=0; j<N; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                list.add(new Employee(a, b));
            }
            Collections.sort(list);//오름차순 정렬
            m.Solve();
        }
    }
}