BOJ 18870 좌표 압축

문제를 분석해보면 새로 생성된 좌표 X`은 Xi > Xj를 만족하는 좌표의 갯수를 의미하는 것을 알 수 있다. 이는 i번째 좌표보다 작은 좌표의 갯수가 압축된 좌표임을 나타내는데, 핵심은 어떻게 특정 좌표보다 작은 좌표의 갯수를 구하는것이다.

 

가장 단순하게 이중 for문을 사용하며 부르트포스 방식으로 탐색한다면 O(n^2) 으로 시간초과가 발생한다. 따라서 다른 방법을 떠올려야한다. 

 

입력을 보았을때 가장 작은  숫자는 항상 0으로 압축이된다. 이를 바탕으로 좌표를 오름차순으로 정렬하고 i=1, i번째 좌표가 i-1번째 좌표보다 클 경우 이전 좌표값에서 1을 증가시켜주는 방법으로 갯수를 파악할 수 있다. 

이 방법을 사용하면 O(n) 만에 특정 값보다 작은 값의 갯수를 구할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b)
{
	return a.second.first < b.second.first;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	vector<pair<int,pair<int, int>>> v; //{num, {idx,cnt}}
	int n;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		v.push_back({ num,{i,0} });
	}
	sort(v.begin(), v.end());


	for(int i = 1; i < n; i++)
	{
		if(v[i].first > v[i - 1].first)
		{
			v[i].second.second = v[i - 1].second.second + 1;
		}
		else
		{
			v[i].second.second = v[i - 1].second.second;
		}
	}

	sort(v.begin(), v.end(), cmp);

	for(int i = 0; i < n; i++)
	{
		cout << v[i].second.second << " ";
	}
}