[백준] 1946: 신입 사원 JAVA

접근

처음에 문제를 아무리 읽어도 테스트 케이스가 이해가 안됐는데, 입력된 값들을 등수가 아니라 점수로 생각하고 있었다(...) 즉 다른 모든 지원자들과 비교했을 때, 서류와 면접 등수 모두가 남들보다 '큰' 경우에는 제외시켜야 한다. 오늘도 문제를 잘 읽자는 교훈을 얻어간다..

 

이 문제는 단순하게 생각하면 이중 for문을 통해 모든 지원자들을 비교하여 카운트하는 방식으로 풀 수 있다. 하지만 N의 최댓값이 10만이기 때문에, O(N^2)의 시간복잡도를 가지면 시간초과가 나게 된다. 서류 점수로 우선적으로 정렬한 후 뒤쪽 값들과만 비교한다면 시간을 조금은 줄일 수 있겠지만, 그래도 2초 안에 통과하기는 어렵다. 따라서 이중 반복문을 단일로 바꾸는 방법을 생각해봐야 한다. 

 

먼저 서류를 기준으로 등수가 높은 순서대로 정렬해보자. 문제에서 주어진 1번째 테스트케이스 예로 들자. 

서류: 1, 2, 3, 4, 5

면접: 4, 3, 2, 1, 5

서류 점수만 본다면, 어떤 지원자는 무조건 자기보다 오른쪽에 있는 지원자들보다 서류 등수가 높다는 것이 보장된다. 그러니 나보다 왼쪽에 위치한 지원자들과 면접 등수로만 비교하면 되는 것이다. 왼쪽에 있는 지원자들보다 내 면접 등수가 낮다면 절대 합격할 수 없다. 따라서 N만큼 돌면서, 면접 등수의 최솟값을 매번 갱신하며 그 값을 비교해주면 된다. 

 

 

코드

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

public class BJ1946 {
    static class Rank implements Comparable<Rank> {
        int doc, interview;

        Rank(int doc, int interview){
            this.doc = doc;
            this.interview = interview;
        }

        @Override // 서류 등수가 높은 순서대로 정렬
        public int compareTo(Rank o) {
            return this.doc - o.doc;
        }
    }

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

        int tc = Integer.parseInt(br.readLine());
        StringTokenizer st = null;

        for (int t = 0; t < tc; t++) {
            int n = Integer.parseInt(br.readLine());
            ArrayList<Rank> arr = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                int doc = Integer.parseInt(st.nextToken());
                int interview = Integer.parseInt(st.nextToken());
                arr.add(new Rank(doc, interview));
            }
            Collections.sort(arr);

            sb.append(solve(arr)).append("\n");
        }
        System.out.println(sb);
    }

    private static int solve(ArrayList<Rank> arr) {
        int cnt = 0;
        int min = 100001; // N의 최댓값

        for (int i = 0, s = arr.size(); i < s; i++) {
            Rank cur = arr.get(i);
            if(cur.interview < min) cnt++;
            min = Math.min(min, cur.interview);
        }

        return cnt;
    }
}