문제 풀이

입력 받은 값들을 정렬을하고 중복을 제거하여 따로 저장을 해두면
입력 받은 값보다 작은 값들의 개수를 lower_bound(이진 탐색)을 통해 찾을 수있다.

처음에는 map을 통해서 작은 값부터 idx를 매겼지만 시간초과로 인해 바꿨다.
아마 lower_bound와는 다르게 입력연산이 추가되면서 시간이 좀 더 걸리는듯 하다.

문제 링크

boj/18870

소스코드

PS/18870.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
using namespace std;

vector<int> v;
int arr2[1000001];
map<int, int> m;
int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
		arr2[i] = v[i];
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

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