결과 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N;
vector<int> nums;
cin >> N;
for (int i = 0; i < N; i++)
{
int tmp;
cin >> tmp;
nums.push_back(tmp);
}
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
for (int i = 0; i < N; i++)
{
int index = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin();
cout << index << ' ';
}
}처음 시도할 때는 lower_bound 대신 find를 사용했는데 시간 초과가 일어났다.
이유는 find 함수는 시간복잡도가 O(N)을 필요로 하는데 lower_bound는 이분탐색으로 O(logN)을 가지기 때문이다.
lower_bound는 정렬된 배열에서 주어진 값보다 같거나 큰 원소들을 찾아 첫번째 위치를 반환한다.
sorted 벡터의 경우 정렬되어 있어 lower_bound로 풀어도 무관하다.
