좌표 압축

실패 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
sortarr = sorted(arr)
for n in range(N):
    idx = sortarr.index(arr[n])
    print(idx)

수를 정렬을 하고나서 그 수보다 작은 수들의 개수는 그 수의 인덱스라는 아이디어로 풀어보려 하였으나, 역시 index함수의 시간이 오래 잡아먹혀 시간초과가 발생했다.

성공 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

sortarr = sorted(list(set(arr)))
dic = {sortarr[l] : l for l in range(len(sortarr))}
for a in arr:
    print(dic[a])

index함수의 수행 시간(N)을 1로 줄이기 위해 dictionary를 사용하여 arr 값을 키값으로 두고 index를 value로 두어 N번을 초기화 하는 용으로만 사용하여 print의 시간을 줄였다.
이 때 sortarr을 초기화 할 때 원본 arr의 중복 값을 제거해야한다.

sortarr = sorted(list(arr))
print(sortarr)
dic = {sortarr[l] : l for l in range(len(sortarr))}
print(dic)
for a in arr:
    print(dic[a])
# [-10, -9, 2, 4, 4]
# {-10: 0, -9: 1, 2: 2, 4: 4}

이처럼 4가 중복되며 마지막 인덱스로 값이 초기화 되어버리기 때문이다.

결과