[백준_1946] 신입사원 (Greedy)

[1]  문제

[2] 접근법

 

[1] 문제에 대한 이해

본 문제는 풀었던 나도 이해에 어려움을 느껴, 설명을 하고 풀이법에 대해 설명하고자 한다.

• 합격기준
  합격을 하기 위해서는 "다른 모들 지원자"와 비교를 하여, 1개 이상은 더 뛰어난 성적을 가지고 있어야 한다.
  즉 2 과목 모두가 단 1명에게라도 모두 미달이 된다면 불합격이 된다는 의미이다. 뿐만 아니라, 순위는 낮을수록 높은 것 이기에! 비교를 할 때, 남들보다 더 낮은 숫자(=높은 순위)가 있는지를 확인 해야한다.

[2]  접근법

 

그렇다면, 어떻게 효과적으로 문제를 해결 할 수 있을까? 

문제를 최근에 여러 개를 풀면서 느낄 수 있었던 점은, 규칙 또는 기준을 세움으로써 미리 정리가 된다면 알고리즘을 효과적으로 풀 수 있다는 사실을 배울 수 있었다. 이를 통해, 문제 해결을 위한 규칙을 찾아 나섰는데! 그 중 가장 효과적인 방법이였던 것은 문제에서 제공한 사실(1개만 더 높아도 ㄱㅊ)을 이용하는 것 이였다.

 

서류 or 면접을 오름차순(= 등수가 높아짐 = 낮은 성적 )으로 정리를 하게 된다면, 가장 1번째에 있는 친구는 무조건 입사를 하게 될 것이고 ! 2등부터는 자신의 전 참가자보다 면접 등수가 높을 경우에 합격을 하면 된다.

.( 그 이유는 그림에서 자세히 설명하겠다 )

 

1등은 서류가 남들보다 가장 높은 순위를 가졌기 때문에 => 적어도 1개는 남들보다 높다 : 합격

2등의 서류 등수는 1등을 제외하고 나머지 사람보다 높다 => 1등보다 면접 등수가 더 높으면 합격

..반복..

 

<주의>

그러나 예를 들어서

1 4

2 5

3 2

 

이런식으로 전개되는 경우

 

2등은 1등보다 서류&면접 등수가 모두 낮기 때문에 불합격을 한다.

이 때, 3등은 4,5등의 서류 등수보다는 높기 때문에 원래 같았으면 2등의 면접 등수와 비교 해야 하지만, 이미 1등보다 낮은 성적이기 때문에 2등과 비교하는 것이 아닌 1등과 비교를 하면된다. (=> 그림에 빨간색으로 적어놓았다 )

 

 

[3] CODE

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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 test_case = Integer.parseInt(br.readLine()); // 테스트 횟수 입력
        
        for(int i=0; i<test_case; i++) {
            int N = Integer.parseInt(br.readLine());
            int[][] apply = new int[N][2];	// 지원자의 서류 및 면접 성적
            int count = 1;
            for(int j=0; j<N; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                apply[j][0] = Integer.parseInt(st.nextToken());
                apply[j][1] = Integer.parseInt(st.nextToken());
                // 지원자의 서류 및 면접 성적 입력
            }

            Arrays.sort(apply, new Comparator<int[]>() {
                @Override
                public int compare(int[] arr1, int[] arr2) {
                    return Integer.compare(arr1[0], arr2[0]);
                } // 서류 성적 오름차순 정렬 (=> 등수의 숫자가 적으면 높은 것이지만 단순한 수로 보게 되면 오름차순 )
            });

            int standard = apply[0][1];	
            for(int j=1; j<N; j++) { 
                if(apply[j][1] < standard) {	
                    standard = apply[j][1];	// 나보다 1단계 높은 친구보다 면접 등급이 높은 경우에만
                                            // 즉, 합격이 될 때만 기준을 변경
                    count ++; // 모두를 충족하면 합격 => COUNT UP
                }
            }
            System.out.println(count);
        }
    }
}