[BOJ] 18870번 - 좌표 압축

<접근 방식>

주어진 값에 대하여 중복을 허용하여 순서를 매기는 문제이다.

간단하게 sort(), vector와 pair 클래스를 이용하여 해결했다.

-- pair<first, second>

 

pair구조체를 sort할 경우 first를 기준으로 오름차순을 진행하고 second값은 first값을 따라간다.

입력값 tmp vector
tmp.first	tmp.second
2	0
4	1
-10	2
4	3
-9	4

 

정렬된 tmp vector
tmp.first	tmp.second
-10	2
-9	4
2	0
4	1
4	3

 

tmp vector의 num값 중복을 고려한 res vector 입력
res.first	res.second
2	0
4	1
0	2
1	3
3	3

 

정렬된 res vector
res.first	res.second
0	2
1	3
2	0
3	3
4	1

<전체 코드>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


vector<pair<int, int>> tmp, res;

int main()
{
	int N, num, count = 0;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num;
		tmp.push_back({ num, i });
	}

	sort(tmp.begin(), tmp.end());
	res.push_back({ tmp[0].second, count });

	for (int i = 1; i < N; i++) {
		if (tmp[i - 1].first == tmp[i].first)
			res.push_back({ tmp[i].second, count });
		else
			res.push_back({ tmp[i].second, ++count });
	}
	sort(res.begin(), res.end());
	for (int i = 0; i < N; i++)
		cout << res[i].second << " ";
}

<문제 링크>

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

18870번: 좌표 압축