[Greedy]BAEKJOON1946 - 신입 사원

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

시간제한은 2초로 널널한 편이다. 문제에 중요시 되는 조건은 아래 하나 뿐이다,

 

서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

시간조건이나 메모리제한이 없다고 가정하고 푼다면 브루트포싱으로 풀 수 있다.

 

1.지원자를 합격그룹의 모든 멤버와 비교해서 자신보다 서류점수와 면접점수 중 하나라도 순위가 낮다면 합격 그룹에넣는다.

2.만약 모두 순위가 높다면 합격그룹에 넣지 않는다.

3.1번 과정을 거치는 동안 만약 합격그룹의 지원자가 현재 비교하는 지원자 보다 모두 순위가 낮다면 그 지원자를 그룹에서 빼버린다.

 

그럼 브루트포싱 방식으로 해결할 수 있다는건 알 수 있다.

이 때 시간 복잡도를 한번 계산해 보는게 좋다. 먼저 지원자를 합격 그룹의 모든 멤버와 비교하는 과정은 O(n)이 걸리게된다.

이 과정을 다시 n번해야한다. 따라서 시간 복잡도는 총 O(n^2)이 걸리게 된다는 것이다.

 

전체 지원자의 수는 상한선이 100,000이므로 n^2의 시간복잡도를 돌린다는것은 2초를 초과하게될 확률이 높다는 것을(사실상 대부분)

알 수 있다. 따라서 우리는 이 시간을 줄여야될 필요성을 느끼게 된다.

 

보통 줄이는 방법은 그리디와 DP등을 생각해 볼 수 있는데

이 방식은 다행히도 점수중 하나를 먼저 비교하고 그 다음  나머지를 비교하는 방식을 취할 경우 해결할 수 있음을 알 수 있다.

가령 만약 서류 심사 성적순으로 만약 정렬이 되있다면, 면접시험 성적만 비교해서 해결할 수 있다는 것이다.

테스트 케이스를 예로 들어보자.

 

3 6
7 3
4 2
1 4
5 7
2 5
6 1

이렇게 정렬안된 테스트케이스가 정렬이 되있다면?

 

1 4
2 5
3 6
4 2
5 7
6 1
7 3

이렇게 정렬이 될건데 이 정렬후에 비교는 아주 쉬워진다.

 

먼저 1,4는 무슨 일이 있어도 그냥 들어가므로 넣는다.

사실 정렬이 되있으므로 앞숫자는 더이상 비교할 필요성이 없다. 그래서 뒷숫자만 우리가 기억해 두자.

그다음 2,5에서 2는 무시하고 5만 보자. 이는 4보다 순위가 낮으므로 채용할 필요가 없다.

3,6역시 마찬가지로 3을 무시하고 6만 보면 4보다 순위가 낮으므로 채용할 필요가 없다.

4,2는 4보다 순위가 높다. 이 때 상한선을 2로 바꿔준다. 현재 까지 채용인원은 2명이다.

5,7은 2보다 낮으므로 무시, 6,1은 2보다 높으므로 상한선을 1로 바꿔주고 채용인원은 3명이다.

7,3은 1보다 낮으므로 무시한다. 따라서 최종 3명이 채용됬음을 알 수 있다.

 

이 때 알고리즘을 좀더 최적화 한다면 1이 등장했을 때 멈추면된다.

물론 코딩테스트에서는 이렇게 해봤자 별 의미없다.

다만 현업에서는 이렇게 멈춰주면 시간을 더 절약할 수 있다.

따라서 이문제는 정렬하기만 하면 전체를 한번 비교하는것으로 끝나는 그리디 문제임을 알 수 있다.

 

변경된 시간복잡도는 정렬하는데 O(nlogn)이 걸리고 순회하는데 O(n)이 걸린다.

순회와 정렬은 별도이므로 O(nlogn)+O(n)이 되며 따라서 O(nlogn)이 걸리게된다.

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 100001

using namespace std;

int T;
int N;
vector<pair<int, int>> arr;
int result = 0;
int mval;

int main() {
    cin >> T;
    int a, b;
    for (int t = 1; t <= T; t++) {
        /*clean*/
        {
            cin >> N;
            arr.clear();
            arr.resize(N + 1, make_pair(0, 0));
            result = 0;
            mval = INF;
        }

        /*init*/
        {
            for (int n = 1; n <= N; n++) {
                cin >> a >> b;
                arr[n].first = a;
                arr[n].second = b;
            }
        }

        /*logic*/
        {
            sort(arr.begin(), arr.end());
            for (int n = 1; n <= N; n++) {
                if (arr[n].second < mval) {
                    mval = arr[n].second;
                    result += 1;
                }
            }
            cout << result << endl;
        }
    }
    return 0;
}