[백준 Java] 1946 신입 사원

문제 링크

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

접근 방법

처음에 문제 이해를 못했다.

1차 점수로 정렬해서 1등을 뽑고 2차 첨수로 정렬했을 때 1등의 2차 점수보다 낮은 사람을 다 탈락시키면 되는건가 싶었는데 아니었다.

정올에서 같은 문제가 있어 반례를 확인해볼 수 있었는데, 다음과 같다

input
10
9 1
5 7
1 8
2 4
10 5
4 10
7 6
3 2
6 9
8 3

output
4

나
7

잘못 생각했던 부분은 1차 점수로 정렬하고 2차 점수로 재정렬하는 것이 아니었다.

1차 기준으로 정렬 후 2차에서 2차 점수가 가장 높은 것을 갱신해나가면서 그보다 낮은 지원자들을 빼는 방법이었다.

코드

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_1946_신입사원 {

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

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

        while (T-->0){
            N = Integer.parseInt(br.readLine());

            int[][] arr = new int[N][2];

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                //서류, 면접
                arr[i][0] = Integer.parseInt(tokens.nextToken());
                arr[i][1] = Integer.parseInt(tokens.nextToken());
            }

            //서류 기준 오름차순 정렬
            Arrays.sort(arr, (a, b) -> a[0]-b[0]);

            int cnt = N;
            int max = arr[0][1]; //서류 1등의 면접 점수 저장
            for (int i = 1; i < N; i++) {
                if(arr[i][1] < max){//현재 1등의 등수보다 i의 면접 등수가 높으면 최대값 변경
                    max = arr[i][1];
                }else{ //현재 1등의 면접 점수보다 낮으면 선발 안 함
                    cnt--;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

뿌듯함을 느꼈으나 시간이 이렇게까지 많이 걸린다고? 싶었다.

어떤 힘을 조금 빌린 결과 정렬이 꼭 필요하지 않다는 것을 알게 되었다.

1차인 서류 등수를 인덱스로 사용하고 2차 면접 점수를 값으로 사용하면 정렬할 필요가 없어진다.

이런 생각 해내는 뇌..당장훔쳐...

코드2

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1946_신입사원 {

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

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

        while (T-->0){
            N = Integer.parseInt(br.readLine());

            int[] arr = new int[N+1];

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                //서류, 면접
                int idx = Integer.parseInt(tokens.nextToken());
                int val = Integer.parseInt(tokens.nextToken());

                arr[idx] = val;
            }

            //서류 기준 오름차순 정렬
            int top = arr[1];
            int cnt = 1; //서류 1등

            for (int i = 2; i <= N; i++) {
                if(arr[i] < top){
                    top = arr[i];
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

만족