백준 No.1946 신입사원 - JAVA

 

 

문제

언제나 최감ㄴ을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원을 선발하고 싶어한다. 

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 a의 성적이 다른 지원자 b의 성적에 비해 서류심사 결과와 면접 성적이 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오

 

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

 

즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이 말이 핵심이다.

 

하지만 코드는 정렬을 하지 않고 주어진다. 그 뜻은 한쪽을 일단 오름차순으로 정렬한다.

왜 오름차순일까? -> 오름차순으로 정렬할 경우 1순위 부터 N순위 까지 정렬된다. 1순위라는 것은 다른 누구보다 높은 점수이기에 비교자체를 할 필요 없이 합격이다.

2순위부터 보자면 2순위의 경우 1순위에게 한 쪽에서 졌다. 그렇다면 다른 쪽이 남았는데 이 다른 쪽도 패배한다면 그대로 탈락이다. 

첫번째 예제를 통해 할 경우

이렇기 때문에 한쪽 정렬이 필요하다. 면접으로 정렬해도 됨

만약 면접을 기준으로 정렬한다면

4   1

3    2

2    3

1    4

5    5

이런식이므로 같은 결과가 나온다.

 

 

근데 여기서 면접 순위가 자신보다 위인 애들 중에서 면접점수가 가장 커야한다..? 이 부분은 가장 큰 값을 temp 변수에 저장해두고 더 큰 값이 나오면 바꿔주면 된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

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

        for(int i = 0; i < N;i++){
            int M = Integer.parseInt(br.readLine());
            ArrayList<int[]> list = new ArrayList<>();
            int count = 1;
            for(int j=0;j<M;j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                list.add(new int[]{a,b});
            }

            list.sort(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });

            int temp = list.get(0)[1];	//첫번째 면접 점수

            for (int j = 1; j <= list.size()-1; j++) {
                if(temp > list.get(j)[1]){	//만약 자신보다 전 등수 면접 점수가 크다
                							//그럼 자신이 등수가 높다는 뜻이므로 temp값변경

                    temp = list.get(j)[1];
                    count++;
                }
            }

            System.out.println(count);
        }
    }
}
//https://sanghyu.tistory.com/36