[백준] 18870번 좌표 압축 ★

💡문제접근

• Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
• 해당 문제의 범위는 1 ≤ N ≤ 1,000,000, -10^9 ≤ Xi ≤ 10^9이므로 2중 반복문을 통한 브루트포스 탐색은 답이 될 수 없다.
• 테스트케이스를 예로 들어 설명하면 다음과 같다.

💡테스트케이스1

입력
5
2 4 -10 4 -9

출력
2 3 0 3 1

• 2보다 작은 수는 -10, -9이므로 2

• 4보다 작은 수는 -10, -9, 2, 2인데 이 때 2는 중복되므로 하나로 계산하여 3

• -10보다 작은 수는 없으므로 0

• 4보다 작은 수는 위에서 구했으므로 3

• 1보다 작은 수는 -10, -9이므로 2

💡코드(메모리 : 154816KB, 시간 : 2004ms)

import sys
input = sys.stdin.readline

N = int(input())
X = list(map(int, input().strip().split()))
# 중복 카운팅을 방지하기 위해 set()을 사용
temp = list(set(X))
temp.sort()
my_dict = {}

for i in range(len(temp)):
    if temp[i] in my_dict:
        pass
    else:
        my_dict[temp[i]] = i

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

💡소요시간 : 28m