[백준] 신입 사원

어찌어찌 테스트케이스는 정확하게 답이 나오는 걸 확인했는데, 시간초과가 계속 나왔다.
아무리 생각해도 반복문 한 번에 해결할 방법은 없는 것 같아서 최대한 효율적으로 탐색하기 위해 check 배열을 이용해 이미 탈락한 경우에는 비교하지 않고 비교의 주체가 되지도 않도록 하였다.

두번째로 질문을 뒤져보니 자료구조의 선언도 뭔가 영향을 주는 것 같아서 배열의 크기를 미리 선언해두고 사용해도 안됐다.

아직 시간초과를 해결할 명확한 방법이 생각나지 않아서 일단은 보류하고 방법을 생각해본 후에 다시 도전해봐야겠다

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

int main(){
	
	freopen("input.txt","rt",stdin);
	int t, n, answer;
	cin>>t;
	
	pair<int,int> v[100000];
	
	int first, second;
	for(int i=0; i<t; i++){
		cin>>n;
		for(int j=0; j<n; j++){
			cin>>v[j].first>>v[j].second;
		}
		
		answer = n;
		//cout<<"answer : "<<answer<<endl;
		int check[n] = {0,};
		
		for(int j=0; j<n-1; j++){
			if(check[j] == 1) continue;
			
			first = v[j].first;
			second = v[j].second;
			//cout<<"first : "<<first<<" second : "<<second<<endl;
			int ff,ss;
			for(int k=j+1; k<n; k++){
				if(check[k] == 1) continue;
				ff = v[k].first;
				ss = v[k].second;
				if(ff<first&&ss<second){
					//cout<<"case1 : "<<v[k].first<<" "<<v[k].second<<endl;
					check[j] = 1;
					answer--;
					break;
				}else if(ff>first&&ss>second){
					check[k] = 1;
					//cout<<"case2 : "<<v[k].first<<" "<<v[k].second<<endl;
					answer--;
				}
				
			}
		}
		cout<<answer<<endl;
	}
}

• 두번째 시도

  구글링을 살짝 해서 힌트를 얻었다.
  중복되는 점수가 없다 -> 인덱스를 이용해 입력받으면서 정렬이 가능하다.

이렇게 했을 때 장점은 처음부터 정렬된 상태를 얻을 수 있고, 한가지만 비교하면 되기 때문에 이전보다 비교횟수도 적어진다.

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

int main(){
	
	freopen("input.txt","rt",stdin);
	
	int t, n, p, c, f, answer;
	cin>>t;
	
	vector<int> v(100000);
	
	for(int i=0; i<t; i++){
		cin>>n;
	
		for(int j=0; j<n; j++){
			cin>>p>>c;
			v[p] = c;
        }
		
		answer = n;
		int check[n] = {0,};
		for(int j=1; j<n; j++){
			if(check[j] ==1 ) continue;
			f = v[j];
			for(int k=j+1; k<=n; k++){
				if(f<v[k]&&check[k] != 1){
					answer--;
					check[k] = 1;
				}
			}
		}
		cout<<answer<<endl;
	}
}

하지만 시간초과.

• 3번째 시도

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

int main(){

	int t, n, p, c, f, answer;
	cin>>t;
	
	vector<int> v(100000);
	
	for(int i=0; i<t; i++){
		cin>>n;
	
		for(int j=0; j<n; j++){
			cin>>p>>c;
			v[p] = c;
        }
		
		answer = n;
        int min = v[1];
		for(int j=1; j<=n; j++){
			if(min<v[j]){
				answer--;
			}else if(min>v[j]){
				min = v[j];
			}	
		}
		cout<<answer<<endl;
	}

}

애초에 정렬된 상태에서 for문을 두번 돌 필요가 없었다.
이미 면접 점수로 정렬돼있다면, 뒤에 있는 것들만 보면 되고 서류 최고점수만 업데이트 해주면서 탐색해주면, check배열도 사용할 필요가 없다.