[백준] 18870번: 좌표압축 (python)

18870번: 좌표압축

---

문제 )

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

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

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

 

 

 

입력 :

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

 

 

 

출력 :

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

 

제한
-   1 ≤ N ≤ 1,000,000
-   -10^9 ≤ Xi ≤ 10^9

 

 

 

 

풀이)

 

나보다 작은 크기를 가진 애들의 수를 출력하면 되는 문제이다.

 

이를 위해서 받은 list를 set을 통해 중복을 제거했고, 정렬을 통해 각 인덱스가 곧 나보다 작은 수의 갯수가 되도록 했다.

 

이후 for문을 통해 li 각 인자의 arr 인덱스를 출력하면 됐다.

 

하지만 list.index는 시간복잡도 O(n)이므로 시간초과가 나게 되므로,

 

한번의 for문을 통해 인덱스와 인자를 딕셔너리화 시켜준 뒤 이를 찾는 방법으로 해결했다.

 

 

n = int(input())
li = list(map(int, input().split()))
 
arr = sorted(set(li))
dic = {}
for i in range(len(arr)):
    dic[arr[i]] = i
 
for i in li:
    print(dic[i], end=" ")

 

---

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

18870번: 좌표 압축