[Baekjoon 18870] 좌표 압축 | Python

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

---

문제

 

좌표를 압축하여 나타내는 문제이다.

압축된 좌표는 $ X_i > X_j $ 를 만족하는 서로 다른 좌표 $ X_j $ 의 개수와 같아야 한다. 가장 작은 수가 0 이 되고 그 이후로 1 씩 커지는 좌표라고 생각하면 좋을 듯 하다.

 

---

풀이

 

주어진 좌표들을 오름차순으로 정렬하고, 정렬된 수의 인덱스를 처음 주어진 좌표들의 순서에 맞게 출력해주면 된다.

단 같은 수는 같은 인덱스를 가져야 하므로 오름차순으로 정렬할 때 중복을 제거해야 한다. 파이썬에서는 set 을 사용하여 간단하게 중복을 제거할 수 있다.

좌표들의 순서에 맞게 인덱스를 정렬하면 가장 작은 수가 0 이 되고 그 이후 수들이 커질 때 마다 1 씩 커지게 된다. 즉 좌표가 압축된다.

 

---

코드

 

coordinate_n = int(input())
coordinate = list(map(int, input().split()))
sort_coordinate = list(set(coordinate.copy()))
sort_coordinate.sort(reverse=False)
dic_coordinate = {}
for i in range(len(sort_coordinate)):
    dic_coordinate[sort_coordinate[i]] = i
for i in coordinate:
    print(dic_coordinate[i], end=' ')