정렬_1946_신입사원

오늘 풀이해 볼 문제는 지난 시간과 동일하게 그리디 알고리즘을 적용하는 정렬파트의 문제이다. 
지난 번에 풀었던 보물보다는 한 번더 생각을 해야 하지만 크게 복잡하지는 않으니 문제부터 보도록 하자.

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

1946번: 신입 사원

문제 분석

• 최대한 많은 신입사원을 뽑아야 한다. 
• 뽑힌 신입사원들 끼리는 우열을 가릴 수 없어야 한다. 
  • 우열을 가릴 수 없다 : 서류 혹은 면접이 나와 다른 한 사람과 비교했을 때 반드시 우세하다.
  • 즉, 두 성적의 석차가 모두 우세해도, 열세해도 안 되는 경우의 수로 신입사원을 최대로 뽑아야 한다.

 

문제 접근 1

• 처음에는 단순하게 예제에 있는 내용을 눈으로 풀어보았다. 
• 특정 대상을 뽑는 다는 가정하에 나머지 지원자들의 성적을 비교하면서 뽑을 수 있는 경우의 수의 최대값을 구해보려 했지만, 구현도 복잡하고, 예외가 너무 많았다. 
• 중요한 것은 시간 제한이 2초 이지만 중첩 for문을 사용하다 보니 문제의 범위만큼 반복을 돌다보면 시간 복잡도는 최악의 경우 100,000^2, 약 100억 번의 연산이 필요하여 시간초과가 날 것이 분명했다. 
• 하여 반복을 한 번만 돌되 최대의 경우의 수를 구하는 방법을 찾아야 한다. 

 

문제 접근 2 

1. 중요한 것은 뽑힌 사원의 성적이 적어도 하나는 다른 사람보다 우수해야 한다는 것이다. 
2. 그렇다면 비교 대상을 서류, 면접이 아니라 하나로 줄일 수 있지 않을까? 
3. 서류 혹은 면접의 순위를 오름차순(점수가 아니라 석차이기 때문에 낮을수록 더 높음)으로 정렬한 후 면접 순위만 바로 이전 사람과 비교하여 면접 순위가 더 높으면  해당 사람을 뽑는 방식으로 바꾸었다. 
4. 정렬한 첫 번째 사원은 서류 성적이 1등이기 때문에 나머지 지원자보다 반드시 한 성적이 우수하기 때문에 무조건 뽑는다고 생각할 수 있다. 이때 이 지원자의 면접 순위를 최소 순위로 저장해놓는다. 
5. 다음으로 비교당하는 지원자는 첫번째로 뽑힌 지원자보다 서류 성적 순위가 밀릴수 밖에 없으니 면접 성적이 반드시 우세해야 한다. 
6. 즉, 최소 면접 순위보다 낮은 사람을 뽑으면서 최소 면접 순위를 갱신해가다 보면 뽑힌 인원은 모두 문제에서 제시한 조건을 만족할 수 밖에 없다. 
7. 서류 면접을 1차적으로 오름차순 정렬했기 때문에 첫 번째로 뽑힌 사람보다 서류 면접이 열세다. 따라서 면접 순위가 우세해야 하는데, 순차적으로 이전 사람보다는 반드시 우세인 지원자만을 뽑았다. 
8. 쉽게 말해 순차적으로 뽑힌 신입 사원들이 서류는 점점 열세 면접은 점점 우세로 뽑혔다는 것이다.
9. 말로만 들으면 난해할 수 있으니 예제1의 테스트 케이스 1번을 시각화해서 그림으로 함께 살펴보면서 이해해보자.

그림

위의 이미지를 보면 초기에 주어진 상태를 서류 성적을 기준으로 오름차순으로 정렬한 결과이다. 
접근에서 설명했듯이 첫 번째에 있는 서류 1등 지원자는 반드시 뽑는다. 
면접 성적의 최소 등급을 4위로 잡아놓으면 이후에 뽑히는 지원자들은 
처음에 뽑힌 지원자보다 서류 성적이 뒤쳐지기 때문에 면접성적이 반드시 우수해야 한다. 
위의 논리대로 진행하다 보면 마지막 5위를 제외하고 4명의 지원자를 선발할 수 있다.

중요한 것은 특정 사람이 서류와 면접 성적을 둘 다 갖고 있어야 하며 한 가지 기준으로 정렬이 가능해야 한다. 
즉, 서류 성적과 면접 성적을 멤버 변수로 갖는 클래스를 생성하여 지원자의 수만큼 클래스 객체를 만든 후에 
객체 정렬을 위해 Comparable 인터페이스를 활용할 것이다. 

코드 구현

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

/**
*	Comparable : this 객체와 파라미터로 들어오는 객체를 비교한다. 
*	Comparator : 파라미터로 들어오는 두 객체를 비교한다. 
*/
class Grade implements Comparable<Grade>{
    int exam;				//서류 순위
    int interview;			//면접 순위

    public Grade(int exam, int interview) {
        this.exam = exam;
        this.interview = interview;
    }

/**
*	양수 (자리바꿈), 0;음수(그대로).	
*	기본이 오름차순 정렬 로직이기 때문에 차이값이 양수가 나온다는 것은 앞에 것이 더 크다는 뜻. 
*   오름차순과  반대이기 때문에 차이 값이 양수일 때만 순서를 바꾸면서 정렬한다.
*   오버플로우를 고려 해야하지만 값의 범위가 0~100,000이므로 overFlow를 고려할 필요가 없기 때문에 차이값을 반환
*/
    @Override
    public int compareTo(Grade o) {
        return this.exam - o.exam;
    }
}

public class _1946 {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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


        //Test Case T개
        while(T --> 0) {
            //시험 지원자수 N명
            int N = Integer.parseInt(br.readLine());

            ArrayList<Grade> gradeList = new ArrayList<>(N);


            for(int i=0; i<N; i++){
                String[] test = br.readLine().split(" ");
                gradeList.add(new Grade(Integer.parseInt(test[0]), Integer.parseInt(test[1])));
            }


            Collections.sort(gradeList);			//접근 3

            int answer = 1;							//접근 4	
            int min = gradeList.get(0).interview;	//접근 4

            for(int i=1; i<N; i++){
                if(gradeList.get(i).interview < min) {	//접근 5
                    answer++;
                    min = gradeList.get(i).interview;
                }
            }

            sb.append(answer);
            if(T > 0) sb.append("\n");
        }//end while

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