#18870 좌표 압축

# 문제

# 입력 및 출력

# 풀이

처음 풀이는 원본과 복사 배열을 하나씩 만들어서 복사배열엔 중복을 없앤 다음

원본 배열과 중복을 없앤 복사 배열을 비교해서 원본 배열의 값이 몇 번째로 큰 값인지 찾도록 했다

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;
vector<int> arr;
vector<int> num;
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		scanf("%d", &t);
		num.push_back(t);
		arr.push_back(t);
	}
	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end());
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = 0; j < arr.size(); j++) {
			if (num[i] > arr[j]) cnt++;
		}
		cout << cnt << " ";
	}
}

찾는 과정에서 이중 for문이 들어가다 보니 시간 복잡도가 커져서 시간 초과 문제가 생겼다

그래서 찾아보니까 이진 탐색 함수로 쉽게 푸는 방법이 있더라

 

lower_bound 함수 사용

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;

vector<int> arr;
vector<int> nrp;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		scanf("%d", &t);
		arr.push_back(t);
		nrp.push_back(t);
	}
	sort(nrp.begin(), nrp.end());
	nrp.erase(unique(nrp.begin(), nrp.end()), nrp.end());
	for (int i = 0; i < n; i++) {
		int result = lower_bound(nrp.begin(), nrp.end(), arr.at(i)) - nrp.begin();
		printf("%d ", result);
	}
}

nrp가 중복을 제거한 복사 배열인데 이 배열내에 원본 배열의 값보다

처음으로 크거나 같아지는 값의 인덱스를 반환하도록 되어있다

 

 

lower_bound 함수는 처음 본다,, 이 함수를 사용하려면 오름차순 정렬이 되어있어야 한다는 전제조건 잊지말기!