-
[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); } } }
'PS > 백준' 카테고리의 다른 글
[백준_20361] 일우는 야바위꾼 ( 구현 [Implementation] ) (0) 2021.01.16 [백준_13419] 탕수육 (구현[implementation]) (0) 2021.01.16 [백준_1541] 잃어버린 괄호 ( Greedy ) (0) 2021.01.05 [백준_2839] 설탕 배달 ( Greedy ) (0) 2021.01.05 [백준_10809] 알파벳 찾기 ( 문자열 ) (0) 2021.01.02 댓글
- 합격기준