좌표 압축

https://www.acmicpc.net/problem/18870

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	54604	22882	17501	39.800%

문제

수직선 위에 N개의 좌표 X₁, X₂, …, X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

X_i를 좌표 압축한 결과 X’_i의 값은 X_i > X_j를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X₁, X₂, …, X_N에 좌표 압축을 적용한 결과 X’₁, X’₂, …, X’_N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, …, X_N이 주어진다.

출력

첫째 줄에 X’₁, X’₂, …, X’_N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -10⁹ ≤ X_i ≤ 10⁹

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2

1 0 1 0 1 0

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 정렬
• 값 / 좌표 압축

---

해결 방법

통과된 코드

#include <iostream>
#include <map>

using namespace std;

int arrN[1000001];
int number[1000000];

map<int, int> myMap;

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> arrN[0];

	for (int i = 1; i <= arrN[0]; i++) cin >> arrN[i];

	// map을 이용한 정렬 
	for (int i = 1; i <= arrN[0]; i++) 
		myMap.insert(make_pair(arrN[i], 0)); 

	int cnt = 0;
	for (auto it = myMap.begin(); it != myMap.end(); it++) 
		it->second = cnt++;

	for (int i = 1; i <= arrN[0]; i++) 
		cout << myMap.find(arrN[i])->second << " ";

	return 0;
}

항상 배열의 범위를 잘못 설정하여 컴파일 및 런타임 에러가 발생한다.