[백준] 1946번 - 신입 사원 [Java]

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

 

[백준] 1946번 - 신입 사원 [Java]

[백준] 1946번 - 신입 사원 [Java]

---

1.  아이디어

 

두 성적 모두 다른 지원자 보다 떨어지는 자는 선발하지 않으므로 한 성적을 기준으로 정렬한 후 순회하며 정렬 기준이 아닌 다른 성적에 대해 이전 모든 지원자 보다 떨어지면 선발하지 않으면 된다.

---

2. 문제풀이

 

성적은 1부터 N 중 중복되지 않는 수 이므로 1차원 배열을 활용해 한 성적을 인덱스, 한 성적은 값으로 하면 인덱스로 한 성적을 기준으로 정렬이 된 것으로 볼 수 있다. 배열을 순회하며 값의 최솟값을 갱신하며 저장하고 이 값을 현재 배열의 값과 비교하면 된다.

---

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

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

            int flag = N;
            int cnt = N;
            for (int i = 1; i < N; i++) {
                flag = Math.min(flag, arr[i]);

                if (flag < arr[i + 1]) cnt--;
            }

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

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기