악곱 == 악성곱슬

정렬

---

이 문제는 다른 ps문제에 많이 응용된다고 하는 좌표 압축을 해보기 위한 문제이다.

데이터의 분포가 넓게 퍼져있는데(-10억 ~ 10억) 정작 해당 값의 정확한 값보다, 순서가 중요한 경우 좌표를 압축해서 구간을 줄여서 다른 알고리즘에 응용할 수 있도록 하는 기법이다.

아이디어는 간단하다. 데이터의 중복을 제거하고, 정렬하여 딕셔너리에 인덱스 번호를 차례대로 부여하는 것이다. 코드는 다음과 같다.

구현

---

import sys

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    li = list(map(int, sys.stdin.readline().rstrip().split()))
    sorted_li = list(sorted(set(li)))
    dic = {sorted_li[i]: i for i in range(len(sorted_li))}
    for i in range(N):
        print(dic[li[i]], end=' ')