[C/C++] 백준 18870번 - 좌표 압축

 

<코드>

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

int N, X, cnt = 0;
vector<pair<int, int>> v, ans;

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> X;
		v.push_back({ X,i }); // {Xi,기존순서}
	}

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

	ans.push_back({v[0].second, 0});

	for (int i = 1; i < N; i++)
	{
		if (v[i-1].first == v[i].first)
		{
			ans.push_back({ v[i].second, cnt }); // {기존순서, Xi'}
		}
		else 
		{
			ans.push_back({ v[i].second, ++cnt }); // {기존순서, Xi'}
		}
	}

	sort(ans.begin(), ans.end());

	for (int i = 0; i < N; i++)
		cout << ans[i].second << " ";
}

 

풀이 방법

 

1. 입력받기(입력받은 순서가 order)

<v벡터>

Xi	order
2	0
4	1
-10	2
4	3
-9	4

 

2. Xi의 크기대로 2차원 v벡터 정렬하기

<v벡터>

Xi	order
-10	2
-9	4
2	0
4	1
4	3

 

3. 앞 뒤의 Xi값을 비교해서 같으면 cnt(카운트)를 그대로 유지하고 다르다면 ++cnt을 해줍니다.

<ans벡터>

order	Xi'
2	0
4	1
0	2
1	3
3	3

v[0].first = -10이고 가장 처음의 값이므로 X0' = 0

v[1].first = -9이고 이전값(v[0].first = -10)과 다르므로 X1' = 1

v[2].first = 2이고 이전값(v[1].first = -9)과 다르므로 X2' = 2

v[3].first = 4이고 이전값(v[2].first = 2)과 다르므로 X3' = 3

v[4].first = 4이고 이전값(v[3].first = 4)과 같으므로 X4' = 3

 

4. ans 벡터를 다시 오름차순으로 정렬하고 정답 출력

<ans벡터>

order	Xi'
0	2
1	3
2	0
3	3
4	1

 

 

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

18870번: 좌표 압축