[알고리즘 PS] 백준 1946번 신입 사원 자바 문제풀이

문제

해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

1946번: 신입 사원

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 Greedy 알고리즘을 이용해서 해결할 수 있는 문제이다.

 

Greedy 알고리즘의 특성답게 핵심 아이디어가 중요한 문제같다.

 

해결법

 

만약 서류 점수던 면접이던 하나라도 1등에게 떨어지면 그 인원은 절대로 입사할 수 없다.

 

즉, 서류 1등보다 면접 점수가 낮은 지원자는 모두 떨어지게 된다.

 

이유는 서류 1등의 면접 등수가 4등이라면, 다른 지원자는 무조건 서류는 1등보다 낮게 되는데, 면접 마저도 1등보다 못한 등수가 나오면 1등보다 항상 뒤쳐지기 때문에 탈락하게 된다.

 

이를 이용해서 서류 등수를 기준으로 정렬을 수행하고, 서류 2등 부터 면접 점수가 서류 1등의 점수보다 높으면 채용하면 된다.

 

대신 매번 면접의 등수를 커트라인으로 갱신시켜줘야한다.

 

if(applicants[i].interview < cutLine) {
    count++;
    cutLine = applicants[i].interview;
}

 

정답 코드

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

        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());

            Applicant[] applicants = new Applicant[n];

            for (int i = 0; i < n; i++) {
                int[] s = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
                applicants[i] = new Applicant(s[0], s[1]);
            }
            Arrays.sort(applicants, (a, b) -> a.paper - b.paper);

            int cutLine = applicants[0].interview;

            int count = 1;

            for (int i = 1; i < applicants.length; i++) {
                if(applicants[i].interview < cutLine) {
                    count++;
                    cutLine = applicants[i].interview;  // ???
                }
            }

            bw.write(count + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static class Applicant {
        int paper;
        int interview;

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

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.