18870번 좌표 압축
https://www.acmicpc.net/problem/18870
아이디어
좌표 압축?
수의 범위가 매우 큰 상태에서 수의 값과 상관 없이 숫자 간의 대소관계만 알면 될 때 이용하는 알고리즘이다.
예제 1번
2 4 -10 4 -9 이므로 중복 제거 + 오름차순 정렬하면
-10 -9 2 4 가 된다. 그리고 앞에서부터 인덱스 0 ~ 3까지 주면 된다.
즉 딕셔너리로 봤을 때 dict[-10] = 0, dict[-9] = 1, dict[2] = 2, dict[4] = 3
맨처음에 주어진 입력 리스트를 보고 딕셔너리 value를 출력하면 된다.
answer => 2 3 0 3 1
코드
n = int(input())
coor = list(map(int, input().split()))
coor_sorted = sorted(set(coor)) # 중복 제거 + 오름차순 정렬
dict = {}
for i in range(len(coor_sorted)):
dict[coor_sorted[i]] = i
for num in coor:
print(dict[num], end=" ")