백준 1946번 : 신입사원 c++

 

서류순위와 면접순위 어느것 하나 낮은것이 없어야한다는 것이 포인트다.

 

1. 서류순위대로 오름차순정렬한다. (1등이 제일 앞에옴)
2. 서류 1등의 면접 순위를 따로 저장한다. (int interview)
3. 서류1등인 인덱스 0을 제외한 인덱스 1부터 n-1까지 중에서 면접순위 값이 interview값보다 작은것을 찾는다.
4. 3번을 통해 발견한 값을 interview 값으로 갱신하고 count를 증가시킨다.
5. 3,4번을 반복한다.

 

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

using namespace std;

int t, n;
const int MAX = 100000;
pair<int, int> arr[MAX];
int result[MAX];

int main(void) {

	cin >> t;
	
	for (int tc = 0; tc < t; tc++) {
		cin >> n;

		for (int i = 0; i < n; i++) {
			cin >> arr[i].first >> arr[i].second;
		}

		// 서류 순위로 오름차순 정렬
		sort(arr, arr + n);

		// 서류 1등의 면접 순위를 저장
		int interview = arr[0].second;

		// 채용가능한 인원 수. 서류 1등을 포함시켜서 1
		int count = 1;

		// 서류1등을 제외한나머지 순위들 중 면접점수로 카운트
		for (int i = 1; i < n ; i++) {
			// 만약 지금까지 채용확정된 사원의 면접최저순위보다 높다면 카운트
			if (arr[i].second < interview) {
				count++;

				// 채용확정된 사원의 면접최저순위를 갱신
				interview = arr[i].second;
			}
		}
		// 테스트케이스별 채용인원을 result 배열에 저장
		result[tc] = count;
	}

	// 채용인원을 출력
	for (int i = 0; i < t; i++) {
		cout << result[i] << '\n';
	}
	
}