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

 

문제풀이방법

1. 중복을 제거하기 위해 Hashmap을 선언하고 arr, arr2배열을 선언하였다(arr2가 원본배열)

2. 만약 이전에 입력이 되지 않았다면 arr에 요소를 추가해 주었다(중복 방지).

3.sort함수를 통해 요소를 정렬한다(arr를 정렬 - arr는 중복이 제거된 배열임-).

4.HashMap에 정렬된 요소의 순서를 넣는다.

5.HashMap에 저장된 값 이용해서 arr2 원본배열을 좌표를 출력한다.

 

이 방식은 시간, 공간복잡도 측면에서 효율성이 떨어진다.

더 좋은 방식으로 다음번에 한번 풀어보도록 하겠다.(다른 분들의 코드를 보니 erase를 이용해서 중복을 제거하고 lower_bound를 이용해서 요소값의 위치를 찾음....)

 

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

int arr[1000001];
int arr2[1000001];

int main(void)
{
	int num = 0;
	unordered_map<int,int> hashMap;

	cin >> num;
	int l = 0;
	for (int i = 0; i < num; i++)
	{
		int k = 0;
		cin >> k;
		arr2[i] = k;
		if (hashMap[k] == 0)
		{
			arr[l] = k;
			hashMap[k]++;
			l++;
		}
	}

	sort(arr, arr + l);

	for (int i = 0; i < l; i++)
	{
		hashMap[arr[i]] = i;
	}

	for (int i = 0; i < num; i++)
	{
		cout << hashMap[arr2[i]] << " ";
	}

	return 0;
}

//입력을 받고 정렬을 한다??