[백준] 좌표압축 (C++)

문제

좌표 압축

해결방법

먼저 좌표, 입력순서, 해당 좌표보다 작은 좌표의 개수를 가지는 구조체 벡터(v1)와 좌표의 정보만가지는 벡터(v2)를 생성하였다. 이후 두 벡터모두 오름차순으로 정렬후 v2는 중복을 제거하여 주고 좌표값보다 작은 값을 저장후 입력 순서에따라 다시 정렬후 출력하는 방식으로 구현을 해보았다.

사용함수

sort
algorithm 헤더에 포함되어있는 함수이다.
sort(a,a+5)와 같이 사용하며 시작점과 끝점이 필요하며 기본적으로 오름차순으로 정렬한다.
다른 기준으로 정렬을 원하면 sort(a,a+5,cmp)사용하고 cmp함수는 원하는 기준으로 작성하면된다.
예시)

bool cmp(int a, int b) //내림차순
{
	return a > b;
}

unique
마찬가지로 algorithm헤더에 포함되어 있으며 중복된 원소들을 제거하여 맨뒤로 보낸뒤 중복된 원소들의 시작위치를 반환한다.
unique(v.begin(),v.end())와 같이 사용한다.
erase
벡터의 원소를 제거하는 함수이다.
v.erase(v.begin()+1)으로 사용시 v[1]을 제거
v.erase(v.begin(),v,end())로 사용시 모든원소를 제거

코드

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

struct coordinate {
	int data;
	int idx;
	int num;
};

bool cmp_data(coordinate a, coordinate b) {
	return a.data < b.data;
}

bool cmp_idx(coordinate a, coordinate b) {
	return a.idx < b.idx;
}


int main() {
	int n, value;
	cin >> n;
	vector<coordinate> v(n);
	vector<int>table;
	for (int i = 0; i < n; i++)
	{
		cin >> value;
		v[i] = { value,i, };
		table.push_back(value);
	}
	sort(v.begin(), v.end(), cmp_data); 
	sort(table.begin(), table.end());
	table.erase(unique(table.begin(), table.end()), table.end());//중복제거
	int table_size = table.size(), k = 0;

	for (int i = 0; i < n; i++) {
		if (table[k] == v[i].data) v[i].num = k;
		else {
			v[i].num = ++k;
		}
	}
	sort(v.begin(), v.end(), cmp_idx);
	for (int i = 0; i < n; i++)
		cout << v[i].num << ' ';

}

맞기는 했지만... 시간이랑 메모리를 너무 많이사용해서 좋은방법은 아닌것 같다.

+다른사람들 풀이 찾아보니까 lower_bound많이 사용하던데 기능은 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있을 때 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음나타나는지 알 수 있다. 이 함수를 사용하면 코드를 더욱 같단하게 할 수 있을것 같긴한데 그건 다음기회에...

++시간 같은 경우는 벡터 대신 배열을 이용하거나 벡터를 포인터를 이용하여 접근한다면 더욱 빠르게 실행이 가능하다고 한다.