[백준] 18870 - 좌표 압축

www.acmicpc.net/problem/18870

18870번: 좌표 압축

• 처음에 보기에 설명이 부족하네? 라고 생각했지만 예제 2개를 보고 정렬 단계에서 제공되는 문제라는 것을 생각하여 풀었을 시 답이 쉽게 나온다.
• 1024ms가 나왔는데, 다른 사람들은 더 빠르게 푼 Case들이 많아 다시 풀어봐야한다.
  
  
• std::sort()와 std::unique()로 vector의 중복을 제거 할 수 있다.

 - std::unique()는 인접한 중복요소를 삭제하지만, vector의 길이에는 변화를 주지않는다.

 - 따라서 std::sort()를 이용하여 vector의 요소를 정렬 후 std::unqiue()를 사용한다.

 - 또한, std::unique()는 쓰레기 앞의 포인터를 돌려주기 때문에 vector::erase()를 이용해 뒤에서 쓰레기를 삭제한다.

 

• std::lower_bound() 란느 이진 탐색 기반의 탐색 기법이 있다.
• 찾으려는 key값이 없으면 key값 보다 큰 가장 작은 정수 값을 찾는다.
• 같은 원소가 여러개 있어도 상관없으며 항상 유일한 해를 구할 수 있다.

 

• vector<>::iterator 에서 현재 index를 구하는 방법

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> test = { 0, 1,2,3,4,5,6,7,8 };
	std::vector<int>::iterator iter = test.begin();

	while (iter != test.end())
	{
		int pos = iter - test.begin();
		printf("%d ", pos);
		++iter;
	}

	return 0;
}

---

- 1024ms

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

#define N_MAX 1000000
#define X_MIN -1000000000
#define X_MAX 1000000000

// compress pair
int main()
{
	// init
	std::ios::sync_with_stdio(false);

	// 
	int N = 0;
	(void)scanf("%d", &N);

	std::vector<int> inputList;
	std::unordered_map<int, int> compPairList;
	inputList.resize(N);
	for (int idx = 0; idx < N; idx++)
	{
		int x = 0;
		(void)scanf("%d", &x);
		inputList[idx] = x;
	}

	// sort and compress
	std::vector<int> copyList = inputList;
	std::sort(copyList.begin(), copyList.end());
	
	int value = 0;
	for (int idx = 0; idx < copyList.size(); idx++)
	{
		if (compPairList.end() == compPairList.find(copyList[idx]))
		{
			compPairList.insert(std::pair<int, int>(copyList[idx], value));
			value++;
		}
	}

	// update
	for (int idx = 0; idx < N; idx++)
	{
		inputList[idx] = compPairList[inputList[idx]];
		printf("%d ", inputList[idx]);
	}
	printf("\n");

	return 0;
}

 

- 668 ms

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

int main()
{
	// init
	std::ios::sync_with_stdio(false);
	

	int N = 0;
	(void)scanf("%d", &N);

	// input
	std::vector<int> inputList;
	for (int idx = 0; idx < N; idx++)
	{
		int num = 0;
		(void)scanf("%d", &num);
		inputList.push_back(num);
	}

	// 중복 제거
	std::vector<int> copyList = inputList;
	std::sort(copyList.begin(), copyList.end());
	copyList.erase(std::unique(copyList.begin(), copyList.end()), copyList.end());

	// printf
	for (int idx = 0; idx < N; idx++)
	{
		int pos = std::lower_bound(copyList.begin(), copyList.end(), inputList[idx]) - copyList.begin();
		printf("%d ", pos);
	}
	printf("\n");

	return 0;
}