호프 2021. 5. 5. 02:34

www.acmicpc.net/problem/18870

 

18870번: 좌표 압축

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌

www.acmicpc.net

문제풀이:

set을 이용하여 중복된 수를 제거한 후, 오름차순으로 정렬하였다.

그리고 처음에 주어진 배열의 원소를 새로 정렬한 배열에서 찾고 그 인덱스를 정답 배열에 추가하였다.

 

pypy로 통과하였다.

 

import sys

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
XX = sorted(list(set(X)))

r = len(XX)-1
ans = []
for i in X:
    left = 0
    right = r
    while (left<=right):
        mid = (left+right)//2
        if (XX[mid]==i):
            ans.append(mid)
            break
        elif (XX[mid]>i):
            right = mid-1
        else:
            left = mid+1

for i in ans:
    print(i, end=" ")