https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
좌표 압축 - 수의 범위가 매우 큰 상황에서 수의 값과 상관없이 좌표들 사이의 대소만 구별할 때 사용
1. 좌표 압축을 할 배열을 임시의 배열에 중복이 없고(set) 정렬된(sort) 상태로 만들어 둔다.
2. 압축할 배열의 각 수들이 임시 배열의 몇 번째 인덱스에 해당하는 수인지 찾는 것으로 대소를 구별한다.
임시 배열은 정렬된 상태이기 때문에 이분 탐색을 이용하기 때문에 시간복잡도 = O(logN)
수 입력 -> 중복값 제거(set) -> 정렬(sort) -> 인덱스 부여(dict)
내 제출
import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr_set = set(arr) # 중복 제거
nums = list(arr_set) # 리스트 복귀
nums.sort() # 정렬
numdict = {}
for i in range(len(nums)): # 딕셔너리 형식으로 인덱스 부여
numdict[nums[i]] = i
for i in arr:
print(numdict[i], end=' ') # 인덱스 출력