백준 18870 좌표압축 파이썬

https://www.acmicpc.net/problem/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을 공백 한 칸으로 구분해서 출력한다.

풀이

내가 푼 방법(시간초과)

import sys

n=int(input())
arr=list(map(int,input().split()))
cnt=0
ans=[]
l=[]
for x in arr:
    for i in range(n):
        if x >arr[i] and arr[i] not in l:
            l.append(arr[i])
    ans.append(len(l))
    l=[]
for x in ans:
    print(x,end='')

시간초과가 난 이유는 문제에서의 제한은 1 ≤ N ≤ 1,000,000로 주어졌는데 나는 O(n^2)로 구현했기 때문이다.
다른 사람들의 풀이를 보니 index로 구현해도 시간초과가 난다고 한다.(파이썬 index의 시간복잡도는 O(N)이다.)
결국 O(nlongn)이하로 구현을 해야하는 문제인 걸로 예상된다.

이 문제는 딕셔너리에서 value를 반환할때 시간복잡도는 O(1)이기 때문에 딕셔너리로 구현을 하는 방법으로 풀어야한다

정답코드

import sys
sys.stdin=open('baekjoon/input.txt','r')
n=int(input())
arr=list(map(int,input().split()))
arr_set=sorted(set(arr)) #중복제거를 위해 리스트를 set로 만든 후 정렬
arr_dict={arr_set[i]:i for i in range(len(arr_set))}#딕셔너리로 저장 -> '숫자:arr_set에서의 해당 인덱스'

for i in arr:
    print(arr_dict[i],end=' ')