[JAVA] 백준 1946- 신입 사원

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

1946번: 신입 사원

 

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

class Test implements Comparable<Test>{
    int a, b;
    public Test(int a, int b){
        this.a = a;
        this.b = b;
    }
    @Override
    public int compareTo(Test o) {
        return this.a - o.a; // 서류 심사 성적으로 오름차순 정렬
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        while(T-->0){
            int N = Integer.parseInt(br.readLine());
            ArrayList<Test> list = new ArrayList<>();
            for(int i=0; i<N; i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                list.add(new Test(a, b));
            }
            Collections.sort(list);

            int highRank = Integer.MAX_VALUE;
            int cnt = 0;
            for(Test t : list){
                if(t.b < highRank) { // 최솟값이 발견되면 (순위가 낮을 수록 좋은 성적임)
                    highRank = t.b; // 최솟값 갱신
                    cnt++; // 신입사원으로 선발
                }
            }
            sb.append(cnt+"\n");
        }
        System.out.println(sb);
    }
}

 

 

서류 심사 성적이나 면접 시험 성적 중 하나를 기준으로 오름차순 정렬한다.(나는 서류 심사 성적을 기준으로 함)

그럼 리스트를 처음부터 순회할 때 서류 심사 성적은 이미 높은 것 부터 정렬되어 있으므로

면접 시험 성적만 보면 된다.

면접 시험 성적이 최솟값보다 작으면, 서류 심사 성적이 자기보다 더 높은 사람이 있더라도 면접 시험 성적은 그사람보다 높은 것이므로 선발된다. 

그렇게 최솟값을 갱신시키면서 선발되는 사원을 카운팅 한다.