18870번 - 좌표 압축

시간제한 : 2초
메모리 제한 : 512MB

---

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

---

입력

첫째 줄에 N이 주어진다.

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

---

출력

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

---

제한

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

---

예제 입력 1

5
2 4 -10 4 -9

---

예제 출력 1

2 3 0 3 1

---

코드

import sys

N = int(sys.stdin.readline().strip())

X = list(map(int, sys.stdin.readline().strip().split()))

X_sort = sorted(list(set(X)))

dic = {}
for i in range(len(X_sort)):
  dic[X_sort[i]] = i

for i in X:
  print(dic[i], end=" ")

---

풀이

시간 : 1976ms
메모리 : 154800KB

먼저 X 리스트에 X'₁, X'₂, ..., X'n를 입력받는다.
sorted()를 이용해 오름차순 정렬한 후 set으로 중복 제거를 해 X_sort에 저장한다.
그 후 for문을 이용해 key로는 작은 좌표부터 큰 좌표 순으로 저장(X_sort[i])하고, value로는 본인 좌표보다 작은 좌표의 개수인 i를 dic에 저장한다.
그 후 입력된 좌표의 순서대로 dic의 value값에 저장되어 있는 본인 좌표보다 작은 좌표의 개수를 출력해준다.