[백준] 좌표 압축

유의할점

시간 복잡도 계산

N = 백만

풀이

정렬후 중복을 포함하지 않는 배열로 만든 배열의 인덱스가 몇개의 수보다 큰지 알려준다.

코드

C++ : O(N)

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

using namespace std;

vector<int> CompCoordinate(vector <int> Coord) {
	vector<int> Coord_ = Coord;
	sort(Coord_.begin(), Coord_.end());
	Coord_.erase(unique(Coord_.begin(), Coord_.end()), Coord_.end());
	map <int, int> m;
	for (int i = 0; i < Coord_.size(); i++)
		m[Coord_[i]] = i;
	for (int i = 0; i < Coord.size(); i++)
		Coord[i] = m[Coord[i]];
	return Coord;
}

int main() {
	int N;
	cin >> N;
	vector <int> Coord(N);
	for (int i = 0; i < N; i++)
		cin >> Coord[i];
	vector <int> CompCoord = CompCoordinate(Coord);
	for (int i : CompCoord)
		cout << i << " ";
}

C++ : 시간 복잡도 계산 안한 코드 O(N^2)

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

using namespace std;

vector<int> CompCoordinate(vector <int> Coord) {
	vector<int> Coord_ = Coord;
	sort(Coord.begin(), Coord.end());
	Coord.erase(unique(Coord.begin(), Coord.end()), Coord.end());
	vector<int> res;
	for (int i : Coord_) {
		int idx = find(Coord.begin(), Coord.end(),i) - Coord.begin();
		res.push_back(idx);
	}
	return res;
}

int main() {
	int N;
	cin >> N;
	vector <int> Coord(N);
	for (int i = 0; i < N; i++)
		cin >> Coord[i];
	vector <int> CompCoord = CompCoordinate(Coord);
	for (int i : CompCoord)
		cout << i << " ";
}