📩 출처
문제
수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.
👉 생각
- 먼저 입력받는 숫자들을 리스트에 중복없이 담기 위해서
set을 해준다. 리스트를 돌면서 숫자가 하나 나오면 그 숫자보다 작은 숫자들의 개수를 담아주면 되지만 이는 시간초과가 발생한다. - 다른방법으로
lst를 정렬해준다면 각 숫자의 인덱스는 해당 리스트에서 자기보다 작은 숫자들의 개수를 의미한다. 따라서 숫자와 인덱스를 딕셔너리의 키(숫자)와 값(키보다 작은 숫자의 개수)으로 설정한 뒤 출력해주면 된다.
import sys
n = int(input())
numbers = list(map(int, sys.stdin.readline().split()))
lst = list(set(numbers))
lst.sort()
result = {}
for i in range(len(lst)):
result[lst[i]] = i
for num in numbers:
print(result[num], end = ' ')