https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 N의 범위가 1,000,000 이므로 O(N^2)의 알고리즘으로는 시간 초과 판정을 받기 때문에 logN의 시간복잡도를 가지고 있는 이진탐색으로 해결할 수 있습니다. 문제의 예시를 설명하면 다음과 같습니다.
2 4 -10 4 -9
2 보다 작은 수는 -10, -9 총 2개 입니다.
4보다 작은 수는 -10, -9, 2 총 3개 입니다.
-10보다 작은수는 없습니다. 총 0개 입니다.
4보다 작은 수는 -10, -9, 2 총 3개 입니다.
-9보다 작은 수는 -10 총 1개 입니다.
따라서 결과는 2, 3, 0, 3, 1 입니다.
다만 두번째 예시에서 알 수 있듯이 중복된 숫자도 고려해줘야 합니다. 즉 다음과 같습니다.
1000 999 1000 999 1000 999
1000 보다 작은 수는 999 총 1개 입니다.
999보다 작은 수는 없습니다. 총 0개 입니다.
1000 보다 작은 수는 999 총 1개 입니다.
999보다 작은 수는 없습니다. 총 0개 입니다.
1000 보다 작은 수는 999 총 1개 입니다.
999보다 작은 수는 없습니다. 총 0개 입니다.
따라서 결과는 1, 0, 1, 0, 1, 0 입니다.
즉 이를 통해서 중복을 제거해줘야 하므로 set 즉 집합을 사용해야하는것을 알 수 있고 집합을 사용하여 정렬한 뒤 이진탐색을 통해 해당 위치를 찾으면 됩니다. 소스코드는 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def find(num, start, last):
while last >= start:
mid = (start + last) // 2
if data2[mid] == num:
return mid
elif data2[mid] > num:
last = mid - 1
else:
start = mid + 1
n = int(input())
data = list(map(int, input().split()))
data2 = set(data)
data2 = list(data2)
data2.sort()
for i in range(n):
print(find(data[i], 0, len(data2)-1), end=" ")
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.14 |
|---|---|
| 백준 알고리즘 7576번: 토마토(Python) (0) | 2022.01.14 |
| 백준 알고리즘 11723번: 집합(Python) (0) | 2022.01.10 |
| 백준 알고리즘 14499번: 주사위 굴리기(Python) (0) | 2022.01.10 |
| 백준 알고리즘 2941번: 크로아티아 알파벳(Python) (0) | 2022.01.07 |