[백준 1946 JAVA] 신입 사원

처음 접근 방법

: 가장 긴 감소하는 부분순열

- 서류심사 등수, 면접 등수가 주어지기 대문에 배열의 index를 서류심사 등수로, 면접등수를 배열의 값으로 넣어주어 가장 긴 감소하는 수열을 찾으면 될 것 같았다. => 시간초과 n^logN

 

다음 접근 방법

: 위의 방식과 같이 서류심사 등수로 정렬을 한다(등수를 배열의 index로 활용하기때문에 입력을 받으며 정렬이 된다)

1등의 면접등수를 min으로 기록하고, 그 값보다 작은 값들만 추린다. min값보다 값이 작다면 answer에 1을 더해주고  min값을 해당 값으로 바꿔준다.(이렇게되면 1등보다 면접등수가 낮고, 서류심사등수가 높은 사람만 선택됨)

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N + 1];
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                arr[a] = b;
            }
            int answer = 1;
            int min = arr[1];
            for (int i = 2; i <= N; i++) {
                if (arr[i] < min) {
                    answer++;
                    min = arr[i];
                }
            }
            System.out.println(answer);
        }
    }
}