7) 백준 1946 - 신입사원

<문제>

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

1946번: 신입 사원

그리디긴 한데.. 시간을 줄이는게 좀 어려웠던 문제였다.

 

<코드>

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	int test_case, N;
	int sc_1, sc_2;
	
	cin >> test_case;
	
	for(int i = 0; i < test_case; i++) {
		int score[100001] = {0, };
		cin >> N;
		for(int j = 0; j < N; j++) {
			cin >> sc_1 >> sc_2;
			score[sc_1] = sc_2;
		}
		
		int cnt = N;
		int min = score[1];
		
		for(int j = 2; j <= N; j++) {
			if(min > score[j]){
				min = score[j];
			}
			else {
				cnt--;
			}
		}
		
		cout << cnt << endl;
	}
	
	return 0;
	
}

원래 했던 생각은 vector에다 pair<int, int>를 넣어서 sorting하려고 했다.

그런데 생각해보니 등수를 매기는 건데 굳이 pair을 써야하나 싶었다.

그래서 나는 배열의 index값을 서류심사 성적 순위로 하고 그에 해당하는 요소를 면접성적 순위로 정했다.

 

처음 생각했던 방식은 다음과 같았다.

for(int j = 1; j < N; j++) {
	if(score[j] != 0) {
		for(int k = j+1; k <= N; k++) {
			if(score[j] < score[k]){
				score[k] = 0;
				cnt--;
			}
		}
	}
}

이미 배열은 서류심사 성적 순위로 정렬되있으므로, 요소(score[k])가 높은게 있으면 0 으로 설정해서 다음에는 그냥 지나가도록 정했다. 이 때 지워지는건 후에 생각 안해도 되는 이유가 score[j]로 지워졌다는 의미는 score[j]로 인해 0으로 바뀔 요소들은 이미 score[j]로 지워지기 때문에 생각하지 않아도 된다.

 

하지만 지금 코드에는 문제가 있다. 시간 복잡도가 O(n^2) (실제로는 더 작겠지만....) 정도 된다. 엄청 시간이 오래걸린다.

 

그래서 다음과 같이 바꿨다.

int min = score[1];
		
for(int j = 2; j <= N; j++) {
	if(min > score[j]){
		min = score[j];
	}
	else {
		cnt--;
	}
}

결론부터 말하자면 시간복잡도는 O(n)으로 매우 줄었다.

score[1]을 따로 저장한 다음에 그 값을 계속 비교해나간다.

크면 min에 넣어주고, 작으면 탈락처리(cnt--)를 시킨다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

나는 1700ms 걸렸다.

그런데 세상에 마상에 이럴수가 저럴수가 400초대로 나오는 사람도 있었다.

허허.......ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ