[백준] 1946 신입사원(C++)

1946번: 신입 사원 (acmicpc.net)

---

난이도 : 실버 1

 

풀이 방법 :

 

문제가 살짝 헷갈렸긴했는데 문제의 의미는

한 사람의 서류등수와 면접등수가 어떠한 다른 사람의 두 등수에 둘 다 지면 안된다는 뜻

 

머튼 해결방법

pair배열을 선언하여, 서류랑 면접점수를 담게 하고,

서류점수를 기준으로 배열을 sort를 한 다음 면접점수에서 배열 순서대로 arr[i] < arr[i+1] 이면 i+1 의 인덱스를 가진 배열이 둘다 점수가 졌다는 의미이므로 cnt변수에 1씩더해준다.

답은 n-cnt를 출력하면 끝! 

 

이제 n이 십만개고 시간제한이 2초이므로 nlogn이하로 풀어야 되는 문제였음 (n제곱이면 시간초과임 !)

 

 

코드 :

 

#include <iostream>
#include <algorithm> 
using namespace std;

int t, n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> n;
        pair<int, int> p[100002];
        for (int i = 0; i < n; i++) {         
            cin >> p[i].first >> p[i].second;
        }
        sort(p, p + n);

        int m = p[0].second;
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            m = min(m, p[i].second);
            if (m < p[i].second) {
                cnt++;
            }
        }
        cout << n-cnt << endl;
    }

}