[백준] 1946 : 신입 사원 (JAVA)

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

 

[풀이과정]

N이 10만이라 두 값을 모두 탐색하게 되면 이중포문이라 시간초과가 나기 때문에 한 값만 비교하게 하는 방향으로 고민했다.

먼저 서류 등수를 기준으로 오름차순 정렬을 한 후 면접 등수를 비교하며 한 번의 탐색으로 값을 구했다.

 

[코드]

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static class Point implements Comparable<Point>{
        int note, interview;
        public Point(int note, int interview){
            this.note = note;
            this.interview = interview;
        }

        @Override
        public int compareTo(Point o){
            return this.note - o.note;
        }
    }


    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++){
            int N = Integer.parseInt(br.readLine());
            init(N);
        }
        /*
        [출력]
        선발 가능한 신입사원의 최대 인원
         */
        System.out.print(sb);
    }

    static void init(int N) throws IOException{
        /*
        [입력]
        1. 테스트케이스 개수 T(1<=t<=20)
        2. 지원자의 수 N (1<=N<=100,000)
        3~N. 서류심사 성적, 면접 성적의 순위(작을수록 높은 점수)
         */
        List<Point> list = new ArrayList<>();
        for(int n = 0; n < N; n++){
            st = new StringTokenizer(br.readLine());
            int note = Integer.parseInt(st.nextToken());
            int interview = Integer.parseInt(st.nextToken());

            list.add(new Point(note, interview));
        }

        Collections.sort(list);

        int cntPass = 1; //서류 1등은 무조건 통과
        int minInterview = list.get(0).interview; // 면접등수 초기화
        //서류 2등부터 탐색
        for(int i = 1; i < N; i++) {
            if(list.get(i).interview < minInterview) { // 이전의 면접등수보다 낮으면(점수가 높으면) 합격
                cntPass++;
                minInterview = list.get(i).interview; // 기준 면접등수 갱신
            }
        }
        sb.append(cntPass).append("\n");
    }
}