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

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

18870번: 좌표 압축

문제 풀이

이 문제는 받은 값들을 정렬해서 인덱싱하고 난 뒤 바뀐 값들을 원래 순서대로 출력하는 문제였다. 

맨 처음에 별 생각 없이 코드를 작성했더니 시간초과가 나왔다. 

그래서 생각한 방법은 pair<int, int> 를 이용해 first에는 입력값을 저장하고, second에는 기존 배열의 순서를 저장했다.

first 값을 기준으로 배열을 정렬한 뒤, cnt라는 새로운 배열을 만들어서 first에는 압축한 좌표를 저장하고, second에는 기존 배열의 순서를 저장한다.

그리고 cnt배열의 second 값인 기존 배열의 순서값을 기준으로 정렬하고 출력을 하는 방식으로 해결했다.

그림으로 간단히 표현

소스 코드

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

vector<pair<int,int>> num;
vector<pair<int, int>> cnt;

bool compare_f(pair<int, int> a, pair<int, int> b) {
	int a_f = a.first;
	int b_f = b.first;
	return a_f < b_f;
}
bool compare_s(pair<int, int> a, pair<int, int> b) {
	int a_s = a.second;
	int b_s = b.second;
	return a_s < b_s;
}

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		num.push_back(make_pair(a, i)); //a는 입력값, i는 원래 출력 순서
	}
	//입력 값을 기준으로 정렬
	sort(num.begin(), num.end(),compare_f);

	cnt.push_back(make_pair(0, num[0].second));
	int j = 0;
	for (int i = 1; i < N; i++)
	{
		if (num[i-1].first == num[i].first)
			cnt.push_back(make_pair(j,num[i].second));
		else {
			j += 1;
			cnt.push_back(make_pair(j, num[i].second));
		}
	}
    // 출력 순서를 기준으로 정렬
	sort(cnt.begin(), cnt.end(), compare_s);

	for (auto x : cnt) {
		cout << x.first << " ";
	}
}