[알고리즘-자바] 백준 1946번 신입 사원

본 글은 다크모드에 최적화되어 있습니다.

문제

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

1946번: 신입 사원

언어

자바 Java

해설

문제에서 주어지는 입력에 주의해야 합니다. 

3 2
1 4
4 1
2 3
5 5

위는 5번의 1차 서류심사와 2차 면접시험의 값입니다. 이 값은 점수를 의미하는 것이 아니라 등수를 의미합니다. 즉, 첫 번째 줄의 3 2는 1차 서류심사의 등수가 3위이고 2차 면접심사의 등수가 2위를 의미합니다.

 

int highestRank1 = 1000000;
int highestRank2 = 1000000;

1차 서류심사와 2차 면점심사의 초기값을 크게 설정합니다. 지원자의 수가 최대 100,000이므로 100,000를 넘는 값으로 설정하면 됩니다.

 

class Pair {
    int rank1;
    int rank2;

    public Pair(int rank1, int rank2) {
        this.rank1 = rank1;
        this.rank2 = rank2;
    }
}

List<Pair> persons = new ArrayList<>();
for (int j = 0; j < n; j++) {
    String[] input = br.readLine().split(" ");
    persons.add(new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1])));
}

총 n명의 지원자 정보를 저장합니다.

 

Collections.sort(persons, (p1, p2) -> p1.rank1 - p2.rank1);

지원자를 1차 서류심사의 랭킹이 높은  순서대로(1, 2, 3, 4, ...) 정렬합니다.

 

for (int j = 0; j < n; j++) {
    Pair pair = persons.get(j);
    if (pair.rank1 < highestRank1 || pair.rank2 < highestRank2) {
        count++;
        if (pair.rank1 < highestRank1)
            highestRank1 = pair.rank1;
        if (pair.rank2 < highestRank2)
            highestRank2 = pair.rank2;
        ;
    }
}

정렬된 n명의 지원자를 모두 탐색합니다. 신규 사원이 되기 위해서는 1차 서류심사 또는 2차 면접심사 등수가 하나라도 다른 지원자보다 높아야 합니다. 앞의 조건을 만족한다면 기존의 1차, 2차 심사 값을 갱신해야 합니다. 

ex. 2번 지원자는 신입 사원이 된다. 이전의 1번 지원자보다 2차 면접심사 등수가 더 높다. 

ex. 1번 지원자는 신입 사원이 된다. 앞에 지원자가 없기 때문에 반드시 신입 사원이 된다.

코드

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

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

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int count = 0;
            int highestRank1 = 1000000;
            int highestRank2 = 1000000;
            List<Pair> persons = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                String[] input = br.readLine().split(" ");
                persons.add(new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1])));
            }
            Collections.sort(persons, (p1, p2) -> p1.rank1 - p2.rank1);
            for (int j = 0; j < n; j++) {
                Pair pair = persons.get(j);
                if (pair.rank1 < highestRank1 || pair.rank2 < highestRank2) {
                    count++;
                    if (pair.rank1 < highestRank1)
                        highestRank1 = pair.rank1;
                    if (pair.rank2 < highestRank2)
                        highestRank2 = pair.rank2;
                    ;
                }
            }
            sb.append(count + "\n");
        }
        System.out.println(sb);
    }
}

class Pair {
    int rank1;
    int rank2;

    public Pair(int rank1, int rank2) {
        this.rank1 = rank1;
        this.rank2 = rank2;
    }
}