[백준 1946번 C/C++] 신입 사원

 

[백준 1946번 C/C++] 신입 사원

 

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

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

www.acmicpc.net

---

 

해결방법

 

탐욕 알고리즘 Greedy Algorithm

 

 

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int t, n; // t: 테스트 케이스 개수, n: 지원자 수
int answer; // 선발할 수 있는 신입사원의 최대 인원수
 
struct Stat
{
	int doc;
	int interview;
 
	Stat(int a=0, int b=0) {
		doc = a;
		interview = b;
	}
 
	bool operator<(const Stat& a) const {
		return doc < a.doc;
	}
};
 
vector<Stat> v;
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> t;
	while(t--)
	{
		cin >> n;
		v.resize(n);
		for(int i = 0; i < n; i++){
			cin >> v[i].doc >> v[i].interview;
		}
		sort(v.begin(), v.end(), less<Stat>());
		for (int i = 0; i < n; i++) {
			cout << v[i].doc << " " << v[i].interview << "\n";
		}
		cout << "\n \n";
 
		answer = n;
		for(int i=0; i<n; i++){
			for(int j=0; j<i; j++)
			{
				if(v[j].doc < v[i].doc && v[j].interview < v[i].interview){
					answer--;
					break;
				}
			}
		}
		
		cout << answer << "\n";
		v.clear();
	}
 
	return 0;
}

 

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int t, n; // t: 테스트 케이스 개수, n: 지원자 수
int answer; // 선발할 수 있는 신입사원의 최대 인원수
 
struct Stat
{
	int doc; // 서류 점수
	int interview; // 면접 점수
 
	Stat(int a=0, int b=0) { // 생성자. 초기값은 0.
		doc = a;
		interview = b;
	}
	
	bool operator<(const Stat& a) const {
		return doc < a.doc;  // 서류 점수가 작은 순서로 정렬하기 위한 비교 연산자 오버로딩.
	}
};
 
vector<Stat> v; // 지원자들의 정보를 저장할 벡터
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> t;
	while(t--)
	{
		cin >> n;
		v.resize(n);
		for(int i = 0; i < n; i++){
			cin >> v[i].doc >> v[i].interview;
		}
 
		sort(v.begin(), v.end()); // 벡터 v를 서류 점수 기준으로 오름차순 정렬한다.
 
		answer = 1; // 첫 사람은 서류순위가 가장 낮으므로 무조건 등록
		int minInterviewRank = v[0].interview; // 현재까지 가장 낮은 면접 순위를 저장하는 변수. 첫 번째 사람의 면접 순위로 초기화한다
		
		for (int i = 0; i < n; i++) 
		{						
			// 만약 현재 (i번째)지원자의 면접 순위가 이전까지 본 최고 면접 순위(minInterviewRank)보다 낮다면 선발한다.
			// 새로 등장하는 (i번째)지원자의 서류점수는 이전에 등장한 지원자보다 같거나 크기 때문에 면접 순위가 더 작은 경우만 선발된다.
            if (v[i].interview < minInterviewRank){
				answer++; // 이 사람도 선발 가능하므로 answer 값을 증가
				minInterviewRank = v[i].interview; // 최고 면접 순위를 현재 지원자의 면접 순위로 갱신. 뒤에 등장하는 사람의 서류순위는 현재 사람과 같거나 더 크다. 따라서 뒤에 등장하는 사람의 인터뷰순위가 더 작은 경우에만 신입사원 채용 기준에 해당한다.
			}
		}
 
		cout << answer << "\n"; // 선발할 수 있는 최대 인원수를 출력
		v.clear(); // 다음 테스트 케이스를 위해 벡터 v를 초기화
	}
 
	return 0;
}

 

 

 

 

---