[백준 18870번][C++] 좌표 압축

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	set<int> s; // set로 중복을 없애고 정렬된 입력 값들을 저장
	vector<int> v(N); // 입력 값들을 입력 순서대로 벡터에 저장

	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;

		v[i] = x;
		s.insert(x);		
	}

	map<int, int> m; // 각 숫자가 몇 번째 숫자에 해당하는지 저장할 map 컨테이너

	int number = 0; // 각 숫자가 가지는 번호

	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
	{
		// 제일 작은 수부터 차례로 번호를 매김
		// 자신보다 작은 수의 갯수이므로 중간에 건너뛰는 숫자는 없음 
		m[*iter] = number++; 
	}

	for (int i = 0; i < v.size(); i++)
	{
		cout << m[v[i]] << " ";
	}

	return 0;
}

---

<풀이과정>

1. N을 입력받고, 값들을 저장할 벡터와 세트를 각각 선언

2. 벡터는 출력 순서를 위한 것이고, 세트는 번호를 매기기 위한 것임

3. N만큼 차례로 입력을 받으며 벡터와 세트에 각각 넣어줌

4. 벡터는 입력 값이 입력 순서대로 저장되고, 세트는 입력 값이 정렬되고, 중복이 제거된 상태로 저장됨

5. 각 숫자가 몇 번째로 작은 수인지를 나타내는지 저장할 map 컨네이너와 해당 번호를 나타내는 변수 number를 선언함

6. iterator를 이용해 set의 각 원소들을 돌면서 map에 *iter를 key로하는 value값을 0부터 증가시키면서 번호를 매긴다.

7. 벡터 v를 돌면서 v의 각 원소들을 key값으로 하는 map의 value값을 출력해준다.

---

<코멘트>

하나씩 비교해서 개수를 세는 것이 아니라 정렬된 순서에 맞게 번호를 매기는 관점으로 풀어야 하는 문제였다.

이걸 생각해내는 것이 조금 어려웠다!

---

<제출결과>