[백준1946] - 신입 사원

[문제]

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

1946번: 신입 사원

 

---

 

[문제풀이 전]

예전에 풀어봤던 문제를 다시 풀어봤는데 그때에 비해 시간을 덜 쓰게 됐는데 차이를 보니 Arrays.sort 와 Collections.sort 의 정렬의 속도 차이가 있다는 사실을 알았다.

Arrays.sort() 는 Dual-Pivot Quict sort 를 활용하는데 시간복잡도가 O(nlongn) ~ O(n^2) 의 속도를 낸다.

Collections.sort() 는 Tim sort로 시간복잡도가 O(nlogn) 으로 일단 Arrays.sort 의 최악과 비교를 했을때 훨등한 속도이다. 이 글을 보는 사람이 있다면 참고하면 좋을법한 내용인 것 같다. 위에 관한 자세한 방법은 여기서는 정리를 따로 하지 않으니 구글에 검색을 해봐서 참고하면 된다.

 

---

 

[문제풀이]

 

우선 제한조건을 확인하니 지원자는 최대 100,000로 N^2 의 복잡도를 가진 방법으로는 해결 할 수 없다.

 

지원자는 서류심사, 면접시험의 성적 순위가 주어진다. 어떤 지원자 A의 성적이 다른 어떤 B 의 성적에 비해 성적이 모두 떨어진다면 그사람은 탈락을 하게된다. 그래서 일단 둘 중 하나의 성적순위로 정렬은 한다.(여기서는 서류심사) 그렇게 된다면 이미 하나의 성적은 비교가 된 상태가 된다. 그 상태에서 다른 나머지 하나의 성적만을 비교하면 된다. 서류순위로 정렬을 했으니 서류순위 1등인 지원자는 다른 어떤 지원자보다 모두 성적이 떨어지는 일은 없다. 그래서 그 사람은 뽑고 시작을 하는데 그의 면접순위를 기준으로 비교를 할 것이다.

그 기준점으로 만약 더 높은 순위의 면접성적을 가진 사람이 있다면 그 사람을 뽑고, 다시 그 지원자의 면접순위를 기준으로 비교를 이어간다. 왜냐하면 해당 지원자의 아래순위는 당연히 서류 순위도 낮을텐데 기준이된 지원자의 면접 순위도 넘지 못하면 탈락이기 때문이다.

 

---

 

[소스코드] 

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

public class Main {
    static class People {
        int interview;
        int document;

        public People(int interview, int document) {
            this.interview = interview;
            this.document = document;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        while(t-->0){
            int n = Integer.parseInt(br.readLine());
            ArrayList<People> people = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int interview = Integer.parseInt(st.nextToken());
                int document = Integer.parseInt(st.nextToken());

                people.add(new People(interview, document));
            }

            Collections.sort(people, new Comparator<People>() {
                @Override
                public int compare(People o1, People o2) {
                    return o1.interview - o2.interview;
                }
            });
            
            int ans = 1;
            int tempRanking = people.get(0).document;
            for (int i = 1; i < n; i++) {
                if (tempRanking > people.get(i).document) {
                    tempRanking = people.get(i).document;
                    ans++;
                }
            }
            sb.append(ans + "\n");
        }

        System.out.println(sb);
    }

}