백준 1946 : 신입 사원

1. 문제 : https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

2. 문제 접근

• 완전 탐색 : 모든 지원자의 점수를 비교해야하므로 $N^2$ -> 최악의 경우 십만 * 십만 = 백억번의 계산이 필요. -> Time Limit
• 정렬 : 두 점수 중 하나를 오름차순으로 정렬한다면 나머지 하나의 최솟값을 갱신해가며 합격한 지원자인지 판단하면 된다. 정렬의 경우 $N\log{N}$이고 이후 배열을 탐색하는 로직은 $N$, 즉, 전체 알고리즘의 복잡도는 $N\log{N}$으로 시간 안에 정답을 추출할 수 있다.

 

3. 문제 해결

1. 두 점수 중 하나를 선택하여 오름차순으로 정렬. 주어진 입력값이 점수가 아닌 순위임을 확인할 것.
2. 나머지 점수를 순차적으로 순회하며 최솟값을 비교 및 저장한다.
3. 최솟값보다 더 큰 순위일 경우, 두 점수 모두 임의의 한 지원자보다 낮은 점수를 획득한 것이므로 탈락.
4. 최솟값보다 더 작은 순위일 경우, 임의의 한 지원자보다 높은 점수를 획든한 것이므로 합격.

 

4. 코드

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

bool compare(vector<int>& a, vector<int>& b)
{
	return a[0] < b[0];
}

int solution(int N, vector<vector<int>>& score)
{
	int answer = 0;
	
	// Sort the array by document review score
	sort(score.begin(), score.end(), compare);

	int min = 100001;
	for (int i = 0; i < N; i++)
	{
		// Not selected if the interview score is low
		if (min <= score[i][1]) continue;

		min = score[i][1];
		answer++;
	}

	return answer;
}

int main()
{
	int T, N;
	
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;

		vector<vector<int>> score;

		for (int j = 0; j < N; j++)
		{
			int a, b;
			cin >> a >> b;
			score.push_back({ a, b });
		}

		cout << solution(N, score) << endl;
	}

	return 0;
}