[백준oj] 1946번 신입 사원

www.acmicpc.net/problem/1946

1946번: 신입 사원

---

 

처음 문제를 풀때 이중 반복문으로 돌며 모든 경우의 수를 따지려했지만, N의 크기가 최대 100000이라, O(N*N)이 되면 시간초과가 날것이 뻔하다.

 

그럼 일단 둘중 하나에 대해서 정렬을 해준다. 문제에 나와있는 예시중

3 2

1 4

4 1

2 3

5 5

 

이것을 서류심사 성적을 기준으로 오름차순 정렬을 하면

1 4

2 3

3 2

4 1

5 5

가 된다.

 

그럼 이제 두번째 면접의 경우만 따져주면 되는데, 서류심사가 자신보다 아래인 사람들하곤 비교할 필요가 없어진다. 왜냐하면 이미 서류심사에서 그들보다 순위가 높기때문에, 자신보다 아래사람때문에 탈락할 일은 없기때문이다.

그럼 이제 자신보다 서류심사 등수가 높은사람(숫자가 낮은 사람들) 하고 비교를 하면되는데, 위에있는 사람들과 모두 비교를 한다고 하면 1+2+3+4+ .... + (n-1) = O(N*N)이 나오니 위의 시간복잡도와 똑같아진다.

 

그럼 자신보다 위의 사람들 중에, 자신과 가장 가까운 통과자와 비교를 해서 통과/탈락을 결정지어보면 답이 나온다.

예를 들어 위에서 서류심사 1등은 무조건 통과다. 서류심사 2등은 1등과 비교해봤을때 통과다. 서류심사 3등은 2등과 비교했을때 통과, 4등또한 통과다, 하지만 5등은 4등과 비교해봤을때 불통이다.

 

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

vector<pair<int, int>> v;

bool compare(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

int main() {
	int t;
	int cnt;
	cin >> t;
	while (t--) {
		cnt = 1;
		v.clear();
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			v.push_back(make_pair(a, b));
		}
		sort(v.begin(), v.end(), compare);
        int index=0;
		for (int i = 1; i < n; i++) {
			if (v[i].second < v[index].second){
            	cnt++
                index=i;
            };
		}
		cout << cnt << "\n";
	}

	return 0;
}

하지만 이렇게 제출하면 sort알고리즘의 시간복잡도 때문에 시간초과가 났다.

 

그래서 시간복잡도 O(NlogN)를 보장할 수 있는 heapSort를 구현해서 문제를 풀어주었다.

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

typedef pair<int, int> ii;

ii heap[100001];
int sz;

void downHeap(int i) {
	int child = i * 2;
	ii temp;
	if (child > sz) {
		return;
	}
	
	if (child + 1 <= sz && heap[child].first < heap[child + 1].first) {
		child++;
	}

	if (heap[i].first < heap[child].first) {
		temp = heap[i];
		heap[i] = heap[child];
		heap[child] = temp;
		downHeap(child);
	}
	else {
		return;
	}
}

void heapSort() {
	while (sz > 0) {
		ii temp;
		temp = heap[1];
		heap[1] = heap[sz];
		heap[sz--] = temp;
		downHeap(1);
	}
}

void buildHeap() {
	for (int i = sz / 2; i >= 1; i--) {
		downHeap(i);
	}
}

int main() {
	int t;
	int cnt;
	cin >> t;
	while (t--) {
		cnt = 1;
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			int a, b;
			cin >> a >> b;
			sz++;
			heap[i].first = a;
			heap[i].second = b;
		}
		sz = n;
		buildHeap();
		heapSort();
		int index = 1;
		for (int i = 2; i <= n; i++) {
			if (heap[i].second < heap[index].second) {
				cnt++;
				index = i;
			}
		}
		cout << cnt << "\n";
	}

	return 0;
}