[백준 1946] 신입사원

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

1946번: 신입 사원

백준 1946 신입사원 문제입니다.

알고리즘 분류는 그리디로 되어 있습니다.

---

풀이

 

알아야 할 부분

• 1차(서류), 2차(면접) 두 가지 시험이 있습니다.
• 이때, 1차와 2차 시험 모두 다른 지원자와 비교했을 때 낮은 점수를 갖고 있다면 탈락입니다.
• 또한, 문제에서 순위를 기준으로 나와있다는 것을 주의해야합니다. ex)1과 5중에서는 1이 더 높은 점수인 겁니다.

 

- 문제를 가장 처음에 봤을 때 직관적으로 '이중 for문으로 풀면 정답을 찾을 수 있겠구나' 라고 생각을 했습니다.

- 하지만, 제한시간이 2초인것을 봤을 때 좀 더 빠른 방법을 찾아야 겠다 생각했습니다.

- 제가 선택한 방법은 1차 시험을 기준으로 정렬시킨 뒤 앞에 사람들과 2차 점수를 비교해서 한명이라도 높은 사람이 있으면 합격하지 못하는 방식을 선택했습니다.

 

코드

package codingtest.baek1946;

import java.io.BufferedReader;
import java.io.IOException;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        for(int i = 0; i<T;i++) {
            int answer = 0;
            int applyCnt = Integer.parseInt(br.readLine());
            int[][] tmp = new int[applyCnt][2];
            for(int j = 0; j<applyCnt; j++) {
                st = new StringTokenizer(br.readLine());
                tmp[j][0] = Integer.parseInt(st.nextToken());
                tmp[j][1] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(tmp, Comparator.comparingInt(row -> row[0])); // 1차 시험을 기준으로 정렬

            int standard = tmp[0][1];
            for(int j = 1; j<applyCnt; j++) {
                if(standard > tmp[j][1]) {
                    answer++;
                    standard = tmp[j][1];
                }
            }
            System.out.println(answer+1);
        }
    }
}