백준 / BOJ / 1946 신입 사원 C++

소개글을 제외한 첫 글입니다!

첫 글인 만큼 가벼운 문제인 줄 알았던 문제를 풀어보겠습니다. (한 번 틀렸다.)

 

백준 1946 신입 사원 입니다.

www.acmicpc.net/problem/1946

1946번: 신입 사원

 

 

제한시간은 2초이고 테스트 케이스는 최대 T=20, 지원자 수는 최대 N=100,000입니다.

 

문제를 풀기 위해 기존에 합격한 지원자들보다 새로운 지원자의 성적이 서류와 면접 모두 낮으면 떨어진다는 것을 알 수 있습니다.

처음에는 지원자 수를 고려 안 하고 그냥 문제를 해석한 그대로 새로운 지원자가 기존의 합격자들의 서류와 면접 점수를 모두 비교하여 모두 낮은지, 하나라도 높은지를 비교하였습니다. O(N^2) 으로 풀었기에 당연히 시간초과가 났습니다.

 

시간 초과가 나지 않기 위해 O(N)으로 푸는 방법을 생각해봅시다. 

문제에서 요구하는 것은 합격자가 최대 몇 명이냐는 것입니다.

합격하는 경우는 기존의 합격자보다 서류와 면접 점수 둘 중 하나가 무조건 높아야합니다.

그렇기 위해 서류 점수 순위를 기준으로 입력받을 때부터 정렬되어 있다면 면접 점수는 서류 순위가 높은 사람 모두보다 높아야합니다. 그렇지 않으면 합격자보다 서류와 면접 모두 순위가 낮은 것이기 때문에 탈락입니다.

 

이를 이용하여 O(N)으로 풀 수 있습니다.

 

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

using namespace std;

int main()
{
	int T, N;

	cin >> T;
	while (T--)
	{
		cin >> N;

		vector<int>app(N);
		int highest;

		for (int i = 0; i < N; i++)
		{
			int a, b;
			cin >> a >> b;
			app[a - 1] = b;
		}
		
		highest = app[0];
		int res = 1;

		for (int i = 1; i < N; i++)
		{
			if (app[i] < highest) {
				highest = app[i];
				res++;
			}
		}

		cout << res << '\n';
		app.clear();
	}
}