#1946 신입 사원

# 문제

# 입력 및 출력

# 풀이

처음에 문제를 풀땐 서류심사 성적과 면접 성적을 둘 다 비교하도록 했다

이미 서류 심사 성적을 내림차순으로 정렬해둔 상태에서 또 비교를 해서 반복문이 3중이 되어 시간 초과 문제가 발생했음

cout, cin 문제일까 싶어서 printf, scanf, \n로 바꿔봐도 문제는 똑같았음

아래가 처음 작성한 코드다

#include <iostream>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
vector < pair<int, int> > a;

int compare() {
	int count = 0;
	for (int i = 0; i < a.size(); i++) {
		if (a[i].first == 1 || a[i].second == 1) {
			count++;
			continue;
		}
		int j = i - 1;
		int right = 1;
		while (j >= 0) {
			if (a[i].first - a[j].first > 0 && a[i].second - a[j].second > 0) {
				right = 0;
				break;
			}
			j--;
		}
		if (right) count++;
	}
	return count;
}

int main() {
	int T, N;
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d", &N);
		for (int j = 0; j < N; j++) {
			int tmp1, tmp2;
			scanf("%d %d", &tmp1, &tmp2);
			a.push_back(make_pair(tmp1, tmp2));
		}
		sort(a.begin(), a.end());
		printf("%d\n", compare());
		a.clear();
	}
}

compare함수에서 while문이 쓸데없이 돌고있는게 문제였다

이미 서류심사 성적을 내림차순 정렬해둔 상태에서 

자신보다 서류심사 성적이 높은 사람들의 면접 성적을 모두 조회할 할 필요가 없는 것이다

 

말이 좀 헷갈리는데 첫번째 케이스로 예를 들어 정리하자면

서류심사 성적으로 내림차순 되어 있어

1 4 
2 3 
3 2
4 1
5 5 

이런식으로 벡터가 정렬되어 있고 3 2 성적을 가진 사람을 기준으로 보면 자신보다 서류 성적이 낮은 사람은 볼 필요가 없기 때문에 1 4, 2 3 인 사람의 면접 성적만 보면 된다

여기서 두명의 면접 성적을 볼 때 가장 높은 면접 성적을 가진 사람을 기준으로 보면 이 사람이 최종적으로 통과할 수 있는지를 확인할 수 있음

세번째 사람을 기준으로 보면 면접 심사를 2등을 했으므로 4등, 3등보다 높은 점수를 받았다

따라서 세번째 사람은 최종적으로 통과한 것이다

 

이걸 코드로 정리하면

#include <iostream>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
vector < pair<int, int> > a;

int main() {
	int T, N, count = 0;
	int minv = 100001;
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d", &N);
		for (int j = 0; j < N; j++) {
			int tmp1, tmp2;
			scanf("%d %d", &tmp1, &tmp2);
			a.push_back(make_pair(tmp1, tmp2));
		}
		sort(a.begin(), a.end());
		for (int j = 0; j < a.size(); j++) {
			if (minv > a[j].second) {
				count++;
				minv = min(minv, a[j].second);
			}
		}
		printf("%d\n", count);
		a.clear();
		minv = 100001;
		count = 0;
	}
}

쓸데없는 compare 함수는 지울 수 있고 반복문도 최대 이중 포문이 된다

minv의 디폴트값을 100,001로 잡은 이유는 등수(N)가 최대 100,000이기 때문이다

 

알고리즘 풀이는 아래 블로그 참고

https://blog.naver.com/PostView.naver?blogId=yscyh&logNo=222457883208&parentCategoryNo=&categoryNo=14&viewDate=&isShowPopularPosts=true&from=search 

[백준 1946번 : 신입 사원] - 시간초과