문제

아이디어

그리디 알고리즘을 풀고 싶어 선택했다.
우선 참가자들을 서류 점수로 오름차순 정렬한다.
정렬한 참가자들을 순회하면서 면접 점수를 확인하고, 현재까지의 면접 최고 점수와 비교한다.
현재까지의 면접 최고 점수보다 낮은 점수를 가진 참가자라면, 반드시 해당 참가자보다 면접 점수와 서류 점수 둘 다 높은 참가자 있음을 의미한다.
반대로 더 높은 점수를 보유한 경우에는, 최고 점수를 갱신한다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static StringTokenizer st;
    static int t;
    static int n;

    static class Applicant implements Comparable<Applicant> {
        int paper;
        int interview;

        Applicant(int paper, int interview) {
            this.paper = paper;
            this.interview = interview;
        }

        public int compareTo(Applicant o) {
            return this.paper - o.paper;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        t = Integer.parseInt(br.readLine());

        PriorityQueue<Applicant> pq;
        int minInterview;
        int ans;
        for (int i = 0; i < t; i++) {
            pq = new PriorityQueue<>();
            ans = 0;
            minInterview = Integer.MAX_VALUE;

            n = Integer.parseInt(br.readLine());

            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                pq.add(new Applicant(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }

            while(!pq.isEmpty()) {
                Applicant a = pq.poll();
                if(a.interview < minInterview){
                    minInterview = a.interview;
                    ans++;
                }
            }
            System.out.println(ans);
        }
    }
}

채점 결과

실버 1 문제라 간단히 풀 수 있었다.