[백준]1946. 신입사원

[문제]

 

www.acmicpc.net/problem/1946

1946번: 신입 사원

[풀이]

 

처음에는 2중 for문 사용해서 하나를 기준으로 현재 지원자를 기준으로 서류 점수가 더 우수한 지원자가 있다면 면접 점수를 비교하는 방식으로 풀었다.

모든 면접자에 대해서 한번씩 모두 비교해야 하므로 당연히 시간초과가 나왔다.

 

따라서 두번째에는 서류 점수를 기준으로 오름차순으로 정렬하고 한명의 지원자를 기준으로 앞에 있는 지원자보다 면접 점수도 낮다면 제외하였다. 이렇게 풀었는데도 시간초과가 발생했다.

 

마지막으로는 서류 점수를 기준으로 정렬하고 현재 지원자보다 서류 점수가 우수한 지원자들 중에서 가장 낮은 면접 점수를 임의의 tmp 변수에 저장해두어 반복문을 한번만 사용해서 풀 수 있었다.

다행히 시간초과가 발생하지 않았다. 

 

 

[코드]

 

시간 : 544ms 

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

#define MAX  100000

using namespace std;

int main(void)
{
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int T,N;
    
    cin >> T ;
    
    for(int i=0;i<T;i++){
        
        int res =1;
        
        vector <pair<int,int>> v;
        
        cin >> N;
        
        for(int j=0;j<N;j++){
            
            int a,b;
            cin >> a >> b;
            v.push_back({a,b});
        }
        
        sort(v.begin(),v.end());
        int tmp = v[0].second;
        
        for(int k=1;k<N;k++){
            if(v[k].second < tmp )  res++;
            if(tmp > v[k].second)   tmp = v[k].second;
        }
        cout << res <<"\n";
    }
    return 0;
}