백준 1946 : 신입 사원

https://www.acmicpc.net/problem/1946

1. 접근

• 처음엔 가장 단순하게 서류 심사 결과와 면접 성적이 같이 나와있으므로, vector안에 pair<int,int> 값을 넣어주었다.
  그리고, first 값을 배열하고, 이후 second 값을 모두 비교해주는 과정을 거쳤다
  => 당연히 시간초과!

• second 값을 모두 비교해주는 과정에서는 반복문을 2개나 겹치게 되므로(t 반복실행까지 따지자면 무려 n^3) 그부분을 수정해야 했다.

• first 값을 오름차순으로 정렬했을 때, i=0~n 까지 돌릴때, 0번째 값은 1번째 값보다 첫번째 성적의 등수가 더 높다.
  -> 그런데 second 값까지 0번째가 1번째보다 높다면 1번째 사원은 떨어질 수밖에 없다.(1 3/ 2 2)
  -> 2번째 사원은, 0번째,1번째 사원들보다 2번째 성적이 높아야하고 3번째 사원은 0,1,2보다 높아야할 것이다

• (1 4 /2 2 /3 1 /4 3) 의 케이스를 생각해보자.
  -> 3번째 사원은, second 값이 1이 되어 합격이다.
  -> 4번째 사원은 이제 1,2,3번째 사원보다 높은 등수를 가져야 한다. 그런데 앞에 3번째 사원이 1이라는 높은 등수를 가지고 있기 때문에 4번쨰 사원은 탈락이다
  => 즉, first 값이 뒤로 갈수록, 그 앞에서 가장 높은 등수를 가진 사람보다 높아야 한다!
  => 모든 값을 비교하지 않고, 최곳값만 뽑아내어 비교해주면 된다!

• 여기에 추가적으로, 등수는 모두 n 자연수이고, 동일한 값이 없기 때문에 굳이 vector<pair<int,int>에 넣지 않고 1차원 배열의 인덱스를 first 값으로 활용하여 정렬과정 없이 정답을 구해주었다.

2. 나의 풀이

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100001
using namespace std;

int score[MAX];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t,n;
	cin >> t;
	
	while(t>0) {
		t--;
		cin >> n;
		memset(score, 0, n+1);
		
		for (int i = 0; i < n; i++) {
			int x, y;
			cin >> x >> y;
			score[x] = y;
		}
		
		int ret = 1;
		int max = score[1];
		for (int i = 2; i <=n; i++) {
			if (score[i] < max) {
				//cout << i << " " << score[i] << "\n";
				max = score[i];
				ret++;
			}
		}
		cout << ret << "\n";
	}

	return 0;
}