[C++] lower_bound, upper_bound, vector의 복사

백준 18870. 좌표 압축

N개의 X좌표가 주어지고, X좌표보다 작은 서로 다른 X의 개수를 출력하는 문제다.
이 때 1 ≤ N ≤ 1,000,000 이고 -10^9 ≤ Xi ≤ 10^9 이다.

lower_bound, upper_bound

x값, 그 값의 인덱스, 그리고 답을 계산해 저장할 수 있는 pair<pair<int, int>, int>> 벡터를 만들어서 어떻게 풀어보려고 했는데 너무 복잡시러워서 뭔가 또 배울 때가 됐다 하고 찾아본 게 lower_bound다.

짝꿍은 upper_bound이며
둘 다 (first, last) 범위에서 이진탐색으로 원소를 탐색한 뒤

• lower_bound: 찾는 값 이상의 값이 나오는 첫 위치 반환
• upper_bound : 찾는 값을 초과하는 값이 나오는 첫 위치 반환

만약 찾고자 하는 값이 없으면 last 주소값을 반환한다.
벡터의 경우 v.end()와 같다.

이진탐색이므로 배열이 오름차순 정렬되어 있어야 하고,
반환값에서 첫 번째 주소를 빼주면 인덱스 값을 받아낼 수 있다.

풀이

먼저 원본 벡터를 입력 받고,
원본 벡터를 복사한 벡터를 만든다.
복벡을 정렬한 뒤 중복값을 삭제해 준 다음,
원본 벡터를 돌며 각 값이 복벡의 어느 인덱스에 위치하는지 출력하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	vector<int> v2(v.begin(), v.end()); // <---- 복사 방법은 여러 개
	sort(v2.begin(), v2.end());
	v2.erase(unique(v2.begin(), v2.end()), v2.end());

	for (int i = 0; i < n; i++) {
		int ans = lower_bound(v2.begin(), v2.end(), v[i]) - v2.begin();
		cout << ans << " ";
	}

	return 0;
}

vector의 복사

코드에서는 vector<int> v2(v.begin(), v.end());를 이용했다.
이거 말고도 vector<int> v2 = v; 또는 vector<int> v2(v);를 쓸 수 있는데

큰 차이는 없지만 begin(), end()가 젤 빨랐고
고 다음이 v2(v), 제일 느린 게 v2 = v 였다.

문바문일지도 ~