[백준] 18870번 - 좌표 압축 (C++) 문제 및 풀이

문제) 백준 - 정렬(Sorting) - 좌표 압축

-> https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

n이 최대 100만이기 때문에 O(nlogn)으로 짜야한다.

좌표의 값과 인덱스를 저장 후 값에 대하여 오름차순으로 정렬한다. 그 후 ans에 압축 적용된 값을 넣는다.

 

 

C++ 소스 코드)

 

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 51
	#define MOD 1000000000
	using namespace std;
	typedef pair<int, int> p;
	bool cmp(p a, p b) {
	return a.second < b.second;
	}
	int n;
	p num[1000001];
	int ans[1000001];
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
	cin >> num[i].first;
	num[i].second = i;
	}
	sort(num, num + n);
	ans[num[0].second] = 0;
	for (int i = 1; i < n; ++i) {
	if (num[i - 1].first == num[i].first)
	ans[num[i].second] = ans[num[i - 1].second];
	else
	ans[num[i].second] = ans[num[i - 1].second] + 1;
	}
	for (int i = 0; i < n; ++i)
	cout << ans[i] << " ";
	return 0;
	}

view raw 18870.cpp hosted with ❤ by GitHub