백준 1946 신입 사원

문제링크 : https://www.acmicpc.net/problem/1946

 

문제 접근

• 문제를 추상화 하면
  • A와 B 과목에서 하나라도 다른 사람에 비해 떨어지면 안됨
• 모두 떨어지는 경우를 구하는게 쉬울듯
• 접근 1 : 각 노드당 모든 노드를 순회하면서 모두 떨어지는 경우를 구할경우
  • O(N^2) > e10 시간초과
• 접근 2 : 하나를 기준으로 나머지 값의 최소값을 갱신
  • A,B 과목이 있을때 A 과목을 기준으로 정렬
  • A과목의 순위가 가장 높은 지원자의 B과목 순위를 최소값의 초기 셋팅
  • A과목 순위가 낮은 것들을 순회
    • A 과목 순위가 낮기 때문에, B과목은 더 순위가 높아야함
    • B과목의 순위를 최소값으로 갱신하면서 순회

 

시간복잡도 계산

• 테스트케이스 : T
• A과목을 기준으로 정렬 : NlgN
• 모든 지원자 순회 : N
• 시간복잡도 : O(T * (NlgN + N)) = O(TNlgN) =20* 1e5 * 20 = 4e7

인트 계산

• 면접 지원자숫자 최대 1e6 > 인트 가능

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
pair<int, int> people[100010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T;cin >> T;
    while(T--) {
        int N; cin >> N;
        for(int i=0; i<N; i++) {
            int a,b; cin >> a >> b;
            people[i] = make_pair(a,b);
        }
        
        sort(people, people+N);
        
        int minv= people[0].second;
        int cnt=0;
        for(int i=1; i<N; i++) {
            // A과목 순위가 높은 사람의 B과목 순위도 순위가 높다면 카운트
            if(minv < people[i].second) {
                cnt++;
            }
            // 최소 순위 갱신, 왜냐하면 다음 사람은 최대값과 비교
            minv = min(minv, people[i].second);
        }
        
        cout << N-cnt << '\n';
    }
    return 0;
}
 

 

문제유형

• 그리디 - 두과목 모두 낮은 경우
  
  • A 과목을 기준으로 정렬한 후
  • A가 가장 높은 사람의 B 점수를 기록
  • A 과목을 순회하면서 B점수를 보다 높은값으로 갱신하며
  • 두과목 모두 낮은 경우 조회