백준 1946번 신입 사원 JAVA

링크텍스트

설명

풀이 흐름 설명

처음에는 문제를 잘못 이해하고 내림차순 정렬로 접근했다.
주어지는 입력이 점수로 착각한 것이다. 하지만 문제를 다시 읽고 정확히 이해한 후 서류 순위를 기준으로 오름차순 정렬하여 풀이를 시작했다.

정렬 후에는 서류 순서대로 1등부터 n등까지 배열된다.
즉 각 지원자는 앞사람보다 서류 점수가 낮다(등수가 뒤로 갈수록 점수가 낮아짐).
이제 면접 점수만 관리하면 된다. 첫 번째 지원자의 면접 점수를 min 변수에 저장하고
이후 지원자가 이 값보다 낮은 면접 점수를 가지고 있으면 합격 처리하고 min을 갱신한다.
이 과정을 반복하면 서류와 면접 모두 조건을 만족하는 최대 지원자 수를 계산할 수 있다.

고민과 해결

처음에는 두 점수의 인덱스를 따로 추적해서 비교하려 했다.
하지만 이 방법은 문제의 본질과 맞지 않았다.
왜냐하면 한 지원자의 탈락 여부는 단일 비교 대상이 아니라 지금까지 통과한 모든 사람과의 비교가 필요하기 때문이다. 따라서 인덱스를 따로 관리하면 비교 대상이 계속 증가하고 시간복잡도가 O(n²)로 커지게 된다.

이를 해결하기 위해 서류 기준 오름차순 정렬 후 면접 점수의 최소값만 관리하는 방식으로 접근했다. 이 방법을 사용하면 매 지원자마다 한 번만 비교하면 되고 전체 시간복잡도는 O(nlogn)으로 효율적이다.

최적화 및 구현 포인트

정렬 기준
서류 점수 기준으로 오름차순 정렬
면접 점수는 따로 정렬할 필요 없이 최소값만 관리

면접 점수 최소값 관리
첫 번째 지원자의 면접 점수를 min에 초기화
이후 지원자의 면접 점수가 min보다 낮으면 합격 처리하고 min 갱신

처음에는 정렬 방향이나 인덱스 추적 등에서 고민이 많았지만 문제의 핵심은 “2차원 비교 문제 → 1차원 최소값 관리 문제”라는 그리디 접근이었다.
서류 순으로 정렬하고 면접 최소값을 갱신하면 항상 최적의 최대 합격자를 구할 수 있다.

이 접근법은 신입 사원 선발 문제뿐만 아니라 파레토 최적(Pareto Optimal) 유형의 문제에서도 유용하게 활용할 수 있다.
시간복잡도: O(NlogN), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());

        while(t-->0){
            int n = Integer.parseInt(br.readLine());

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

            for(int i=0;i<n;i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arr, (a,b)-> a[0]-b[0]);

            int count = 1;
            int min = arr[0][1];
            for(int i=1;i<n;i++){
                if(min>arr[i][1]){
                    min = arr[i][1];
                    count++;
                }
            }

            sb.append(count).append("\n");
        }

        System.out.print(sb);
    }
}