Informatica Online Judge

  좌표 압축 [1812 / 0714]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 216   Total Tried : 618


The Champion of this Problem (C++) : gs17044 - ms / 300byte
My Best Submission (C++) : N/A

[JKJeong 2017]

Background

좌표압축이란 주어진 좌표값의 max를 최소화 할 수 있도록 좌표값을 재부여하는 방법을 의미한다.

좌표값이 재부여되어도 원래 좌표의 위치관계는 그대로 유지되어야 한다.

예를 들어 수직선 상의 세 점 a, b, c의 좌표가 999, 83, 1010201 이라면

이 좌표를 2 1 3 으로 바꾸면 세 점의 위치관계는 유지되면서 1부터 3까지의 값으로 모두 표현할 수 있게 된다.

이러한 좌표압축은 다양한 문제를 해결하는데 활용된다.

수직선 상의 n개의 점을 입력받아 각 점의 좌표를 1부터 n이하의 자연수를 이용하여 압축하여 출력하는 프로그램을 작성하시오.

단, 출력된 값의 최댓값이 최소가 될 수 있도록 프로그램을 작성하시오.

Input

첫 번째 줄에 점의 수 n이 입력된다.

두 번째 줄부터 n줄에 걸쳐서 각 점의 좌표가 입력된다.

[입력값의 정의역]

2 <= n <= 100,000
-1,000,000,000 <= 주어진 점의 좌표 <= 1,000,000,000

Output

압축된 각 점의 좌표를 공백으로 구분하여 출력한다.

IO Example

입력1
3
999 83 1010201

출력1
2 1 3

입력2
4
999 9999 999 9

출력2
2 3 2 1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]