문제
수직선 위에 N개의 좌표 X1, X2,..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2,..., XN에 좌표 압축을 적용한 결과 X'1, X'2,..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2,..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- -10^9 ≤ Xi ≤ 10^9
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import sys
read = sys.stdin.readline
n = int(read())
x = list(map(int, read().split()))
s = sorted(list(set(x)))
for i in x:
l, r = 0, len(s) - 1
while l <= r:
mid = (l + r) // 2
if s[mid] == i:
print(mid, end=' ')
break
elif s[mid] < i:
l = mid + 1
else:
r = mid - 1
|
cs |
시간초과때문에 상당히 고생했던 문제다.
lower_bound나 이분 탐색이나 별로 시간 차이가 없을 거 같아서 이분 탐색으로 풀었다.
pypy는 통과가 되는데 파이썬은 시간 초과에 걸린다.
8초면 충분한 거 같은데 원인이 뭔지 모르겠다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 2676 라스칼 삼각형 (0) | 2020.12.07 |
|---|---|
| 백준 온라인 저지 1406 에디터 (0) | 2020.12.07 |
| 백준 온라인 저지 14698 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) (0) | 2020.12.02 |
| 백준 온라인 저지 2589 보물섬 (0) | 2020.12.01 |
| 백준 온라인 저지 6593 상범 빌딩 (0) | 2020.12.01 |
