[BOJ 그리디] 신입사원 1946.JAVA

문제 링크 : https://www.acmicpc.net/problem/1946
문제 등급 : Silver I

1946번: 신입 사원

문제 해결 로직

1. 서류 순위와 면접 순위 중 서류 순위를 기준으로 오름차순으로 정렬한다.
2. 첫 번째 면접자는 서류 순위 중 1등이기 때문에 합격이다.
3. 첫 번째 면접자의 면접 순위를 기준으로 면접 순위가 작은 면접자를 찾아 합격시킨다.
4. 면접 순위가 작은 면접자를 기준으로 보다 작은 면접 순위를 가진 면접자를 합격시킨다.
5. 4번을 반복하여 합격자의 수를 카운트한다.

이 문제의 핵심은 문제를 잘 읽고 해석하는 것이었다.

다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙에서 많이 헷갈렸다.

처음에는 서류 순위 기준으로 정렬 후 바로 다음 지원자와 비교하여 합격을 판단하였다.

하지만 잘 못된 로직이었고 합격한 사람을 기준으로 더 나은 성적을 가진 지원자가 합격하는 것이었다.

구현 자체는 어렵지 않았으나 문제를 해석하는 게 어려웠다.

 

아래와 같이 소스를 공유드립니다.

public class 신입사원 {
    public static class Node {
        int g1, g2, sum;
        Node(int g1, int g2, int sum) {
            this.g1 = g1;
            this.g2 = g2;
            this.sum = sum;
        }
    }
    public static Comparator<Node> compare = new Comparator<>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o1.g1, o2.g1);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < n; i++) {
            int t = Integer.parseInt(br.readLine());
            List<Node> list = new ArrayList<>();
            for (int j = 0; j < t; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                int g1 = Integer.parseInt(st.nextToken());
                int g2 = Integer.parseInt(st.nextToken());
                list.add(new Node(g1, g2, g1+g2));
            }

            list.sort(compare);

            int cnt = 1;
            int c = list.get(0).g2;
            for (int j = 1; j < list.size(); j++) {
                if(c > list.get(j).g2) {
                    cnt++;
                    c = list.get(j).g2;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb.toString());
    }
}