[Baekjoon] 1946번: 신입 사원 - Java

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

1946번: 신입 사원

문제 설명

지원자들을 가장 많이 뽑을 수 있는 선에서 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 낮지 않은 사람들만 필터링해야 한다. 이게 무슨 말인지 필자도 처음 문제를 읽었을 때 이해하지 못했다. 예제 입력을 활용하여 설명하면 다음과 같다.

테스트 케이스 1

	서류 심사 등수	면접 심사 등수
A	3	2
B	1	4
C	4	1
D	2	3
E	5	5

A가 합격했다고 하자. 그렇다면 다른 합격자들 중에서는 A의 서류 심사 등수 또는 면접 심사 등수가 A보다 낮으면 안 된다. B는 A보다 면접 등수는 낮지만 서류 심사 등수가 높으므로 합격이다. C는 A와 B보다 서류 등수가 낮지만 면접 등수가 높으므로 합격이다. D는 A, C보다 서류 심사 등수가 높고 면접 등수가 B보다 높으므로 합격이다. 하지만 E는 서류 등수, 면접 등수 모두 낮기 때문에 불합격이다.

결과적으로 A, B, C, D가 합격하게 되어 총 4명이 된다.

테스트 케이스 2

	서류 심사 등수	면접 심사 등수
A	3	6
B	7	3
C	4	2
D	1	4
E	5	7
F	2	5
G	6	1

A가 합격했다고 하자. B는 A보다 면접 등수가 높으므로 합격이다. C는 A, B보다 면접 등수가 높으므로 합격이다. 이때 문제가 발생한다. B는 C보다 서류와 면접 등수가 모두 낮기 때문이다. 따라서 B는 합격자에서 제외된다. D는 A, C보다 서류 등수가 높으므로 합격이다. 여기서 또 문제가 생긴다. A는 D보다 서류 등수와 면접 등수가 모두 낮기 때문이다. 그렇기 때문에 A는 합격자에서 제외된다. E는 C, D보다 서류, 면접 등수가 모두 낮으므로 불합격이다. F는 D보다 서류, 면접 등수가 모두 낮기 때문에 불합격이다. G는 C, D보다 서류 등수는 낮지만 면접 등수가 높으므로 합격이다.

결과적으로 C, D, G가 합격하게 되어 총 3명이 된다.

풀이 방법

이제 어떤 규칙인지 이해할 수 있을 것이다. 예제를 잘 읽어보면 문제를 해결하는 간단한 방법은 서류 등수 기준으로 정렬한 후에 면접 등수를 기준으로 비교하는 것이다. 먼저 비교 대상을 서류 등수가 1등인 지원자로 선정한다. 그리고 면접 등수가 비교 대상보다 높다면 비교 대상을 해당 지원자로 비교 대상을 바꾼다. 이런 식으로 필터링 해나가면 최대로 신입을 뽑을 수 있는 방법이 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ1946 {

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int T = Integer.parseInt(br.readLine());

            for (int i = 0; i < T; i++) {
                int N = Integer.parseInt(br.readLine());

                CandidateRank[] ranks = new CandidateRank[N];
                String input;
                String[] tokens;

                for (int j = 0; j < N; j++) {
                    input = br.readLine();
                    tokens = input.split(" ");
                    ranks[j] = new CandidateRank(Integer.parseInt(tokens[0]),
                            Integer.parseInt(tokens[1]));
                }

                Arrays.sort(ranks);

                CandidateRank standardCandidateRank = ranks[0];
                int countOfSuccessfullCandidates = 1;

                for (int j = 1; j < N; j++) {
                    if (standardCandidateRank.getInterviewRank() > ranks[j].getInterviewRank()) {
                        standardCandidateRank = ranks[j];
                        countOfSuccessfullCandidates += 1;
                    }
                }
                System.out.println(countOfSuccessfullCandidates);

                // 사용하지 않게 된 객체들을 명시적으로 null 처리하는 뒤처리 작업
                for (int j = 0; j < ranks.length; j++) {
                    ranks[j] = null;
                }
                ranks = null;
                standardCandidateRank = null;
            }
        }
    }

    static class CandidateRank implements Comparable<CandidateRank> {
        private int documentRank;
        private int interviewRank;

        public CandidateRank(int documentRank, int interviewRank) {
            this.documentRank = documentRank;
            this.interviewRank = interviewRank;
        }

        public int getDocumentRank() {
            return documentRank;
        }

        public int getInterviewRank() {
            return interviewRank;
        }

        public void setDocumentRank(int documentRank) {
            this.documentRank = documentRank;
        }

        public void setInterviewRank(int interviewRank) {
            this.interviewRank = interviewRank;
        }

        @Override
        public int compareTo(CandidateRank o) {
            return Integer.compare(this.documentRank, o.documentRank);
        }
    }
}