[C++][좌표 압축 18870] 정렬, 벡터 복사, 중복 제거 ,lower_bound

백준 좌표 압축

 

문제 풀이는 간단하다.

복사해서 정렬 후 작은 것 수 출력하면 된다.

 

이때 필요한 벡터 복사, 중복 제거, lower_bound 사용법 기억해두자

 

1. 벡터 복사

//방법1 
v2.assign(v1.begin(),v1.end());

//방법2 
copy(v1.begin(),v1.end(),v2.begin());

 

2. 벡터 중복 제거

방법1.

vector<int> v({1,1,1,2,2,2,3,3});
sort(v.begin(),v.end());
//v.erase(unique(v.begin() , v.end() ));
//이렇게 하면  전체 중복 제거 못함  
v.erase(unique(v.begin() , v.end() ) , v.end());

sort 후에 unique와 erase 통해서 중복 제거

 

방법2.

set과 assign 사용

vector의 assign은 인자로 시작 iterator와 끝 iterator 받아 이 사이에 있는 값들로 벡터 만들어주는 것

set 은 중복된 원소를 여러개 갖지 않음(중복으로 여러개 가질 수 있는 건 multiset)

set<int> st({1,1,1,2,2,2,3,3});
vector<int> v;
v.assign(st.begin(),st.end());

 

3. lower_bound

<algorithm> 헤더

lower_bound, upper_bound 정상 작동하기 위해서 sort로 오름차순 또는 내림차순으로 정렬되어 있어야함

이진탐색으로 구현되기 때문

vector<int> v ={-2,-2,-1,0,0,1,1,2,3,4};
int index = lower_bound(v.begin(), v.end(), 0 )  - v.begin(); //3
// 0 이상인 첫 번째 원소 위치 반환

int index2 = upper_bound( v.begin(), v.end(), 0 ) - v.begin(); //5
// 0 초과하는 첫 번째 원소의 위치 반환

 

 

 

[통과 코드]

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vector<int> v,cv;
	for(int i = 0,tmp ; i < n ; i++){
		cin>>tmp;
		v.push_back(tmp);
	}
	cv.assign(v.begin(),v.end());  
 
	sort(cv.begin(),cv.end());
	cv.erase(unique(cv.begin(),cv.end()), cv.end() ); 
	string answer;	
	for(int i = 0 ; i < n ; i++){
		auto it = lower_bound(cv.begin(),cv.end(), v[i]);
		answer += (to_string( it-cv.begin() ) +" " );	
	}

	cout<<answer;
}

 

[시간초과코드]

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vector<int> v,cv;
	for(int i = 0,tmp ; i < n ; i++){
		cin>>tmp;
		v.push_back(tmp);
	}
	cv.assign(v.begin(),v.end()); // 복사  
	/* vector copy
		방법1 
		v2.assign(v.begin(),v.end());
		
		방법2 
		copy(v.begin(),v.end(),v2.begin());
	*/
	//다른 사람 풀이 확인  
	sort(cv.begin(),cv.end());
	cv.erase(unique(cv.begin(),cv.end()), cv.end() ); //전체 중복제거  
 	//중복제거 https://sgc109.tistory.com/99 
	string answer;	
	for(int i = 0 ; i < n ; i++){
		auto it = lower_bound(cv.begin(),cv.end(), v[i]);
		answer += (to_string( it-cv.begin() ) +" " );	
	}

	for(int e : v){
		int cnt = 0;
		for(int e2 : v2){
			if(e2 < e) cnt++;
			else break;		
		}
		ans.push_back(cnt);		
	}
	
	string answer;
	for(auto e : ans){
		answer += (to_string(e) + " ");
	}
	cout<<answer;
}

내가 봐도 마지막 마무리가 지저분하다.

 

 

참고

18870 풀이 참고

벡터 중복 제거

lower_bound