BOJ 1946 - 신입 사원

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

1946번: 신입 사원

 

 

1. 아이디어

 

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 것은 고등학교때 배운 여사건을 생각해보면 서류 심사 성적와 면접 시험 성적 모두 다른 지원자보다 떨어지는 경우만 탈락한다는 뜻이다. 

 

모든 지원자의 서류 점수와 면접 점수, 그리고 탈락 여부 정보를 volunteer 클래스로 묶어주고 서류 점수를 기준으로 오름차순 정렬해준다.

static class volunteer implements Comparable<volunteer> {

    int A;
    int B;
    boolean result;

    @Override
    public int compareTo(volunteer o) {
        return A - o.A;
    }
}

 

두 성적 모두 떨어지는 경우만 탈락시키면 되므로 처음엔 모두 합격인 것으로 초기화해준다.

 

[입력]

 

5
3 2
1 4
4 1
2 3
5 5

 

입력이 위와 같다면 오름차순 후 다음과 같이 될 것이다.

5
1 4
2 3
3 2
4 1
5 5

 

정렬 후 첫 번째 지원자의 면접 점수를 기준으로 잡은 후 for 문을 통해 다음 지원자의 면접 점수를 비교한다.

다음 지원자의 서류 점수는 정렬이 된 상태이므로 무조건 순위가 낮을 것이고 면접 점수를 비교해서 탈락자를 걸러낸다.

 

기준 pivot 점수보다 큰 경우 서류 점수와 면접 점수가 둘 다 떨어지는 경우이므로 탈락 체크해준다.

 

그렇지 않을 경우엔 합격자이므로 pivot을 갱신해준다. 여기서 pivot을 갱신해주는 이유는 서류 점수는 정렬이 된 상태라 자동으로 순위가 낮아질 것이고 이전 사람보다 면접 점수 순위마저 낮아지면 탈락이기 때문에 다음 지원자와의 비교를 위해 갱신해주는 것이다. 

따라서 pivot은 높은 순위로 갱신될 것이다. 이 순위를 넘지 못하면 탈락! 서류 순위는 이미 낮기 때문!

int pivot = vols[0].B;
for (int i = 1; i < N; i++) {

    // pivot 보다 큰 경우 둘 다 순위가 낮으므로 탈락
    if (pivot < vols[i].B) {
        vols[i].result = false;
    } else {
        // pivot 갱신
        pivot = vols[i].B;
    }
}

 

2. 시간 복잡도

테스트 케이스가 20개 미만이고 N의 최댓값이 100,000이다.

 

for문을 돌 때 O(N), 정렬할 때 O(N logN)이므로 2초안에 충분히 가능하다.

 

 

 

3. 구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static volunteer[] vols;
    static int N;

    static class volunteer implements Comparable<volunteer> {

        int A;
        int B;
        boolean result;

        @Override
        public int compareTo(volunteer o) {
            return A - o.A;
        }
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());

            StringTokenizer st;
            vols = new volunteer[N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                vols[i] = new volunteer();

                vols[i].A = Integer.parseInt(st.nextToken());
                vols[i].B = Integer.parseInt(st.nextToken());
                vols[i].result = true;
            }

            pro();

        }
    }

    static void pro() throws IOException {
        Arrays.sort(vols);

        int pivot = vols[0].B;
        for (int i = 1; i < N; i++) {

            // pivot 보다 큰 경우 둘 다 순위가 낮으므로 탈락
            if (pivot < vols[i].B) {
                vols[i].result = false;
            } else {
                // pivot 갱신
                pivot = vols[i].B;
            }
        }

        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (vols[i].result == true) {

//                bw.write(vols[i].A +  " " + vols[i].B+"\n");
                cnt++;
            }
        }

        bw.write(cnt+"\n");

    }

    public static void main(String[] args) throws IOException {
        init();

        bw.close();
    }

}