[백준, BOJ] 18870 - 좌표 압축

1. Question

수직선 위에 N개의 좌표 $X_1, X_2, ..., X_N$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

$X_i$를 좌표 압축한 결과 $X'_i$의 값은 $X_i > X_j$를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

$X_1, X_2, ..., X_N$에 좌표 압축을 적용한 결과 $X'_1, X'_2, ..., X'_N$를 출력해보자.

1.1 Input

첫째 줄에 $N$이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 $X_1, X_2, ..., X_N$이 주어진다.
$1 ≤ N ≤ 1,000,000$
$-10^9 ≤ X_i ≤ 10^9$

1.2 Output

첫째 줄에 $X'_1, X'_2, ..., X'_N$을 공백 한 칸으로 구분해서 출력한다.

1.3 Example

입력	출력
5 2 4 -10 4 -9	2 3 0 3 1
6 1000 999 1000 999 1000 999	1 0 1 0 1 0

2. Approach

각 원소가 집합에서 몇번째로 작은지 출력하는 문제.

필자는 중복제거 후, 정렬하고 각 원소 순서대로 어디에 있는지 이진검색을 하며 풀었다.

최소 힙을 쓰는 방법도 있다더라.

 

3. Submission

4. Code

import sys
from bisect import bisect

rl = sys.stdin.readline

N = int(rl())

nums = list(map(int, rl().split()))

mapped_nums = sorted(list(set(nums)))

for i in nums:
    print(bisect(mapped_nums, i, lo=0, hi=len(mapped_nums))-1, end=' ')