BOJ : https://www.acmicpc.net/problem/1517
github : https://github.com/junho0956/Algorithm/blob/master/1517/1517/%EC%86%8C%EC%8A%A4.cpp
버블소트는 O(N^2) 의 시간복잡도를 가지는 정렬입니다.
현재 인덱스를 기준으로 다음 인덱스와 비교하여 swap 이 이루어지는 형태의 정렬인데
이 문제는 최대크기가 50만개이므로 O(N^2) 의 시간복잡도로 문제를 해결하면 시간초과를 받게 될 것 입니다.
swap이 이루어지는건 크기가 작은 인덱스가 크기가 큰 인덱스보다 뒤로 밀려날 때 입니다.
이를 분할정복을 이용하여 해결할 수 있습니다.
보통 분할정복을 이용한 정렬이 merge_sort 와 quick_sort 가 있으며
그 중 우선 분할 후 합치는 과정을 거치는 merge_sort 를 이용하여 문제를 해결할 수 있습니다.
이 문제를 이용하면 inversion 과 같은 도치수도 쉽게 풀 수 있습니다.
partition 단계에서 왼쪽과 오른쪽을 비교했을 때 만약 오른쪽이 왼쪽보다 작다면
=> 왼쪽의 남은 확인하지않은 인덱스들은 오른쪽보다는 당연히 큰 값으로 남아있으므로
그 수만큼 갯수를 더해주면 됩니다.
더보기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <iostream>
using namespace std;
#define MAX 500000
int arr[MAX];
int dup[MAX];
long long partition(int s, int m, int e) {
int left = s, right = m + 1;
int index = 0;
long long result = 0;
while (left <= m && right <= e) {
if (arr[right] >= arr[left]) {
dup[index++] = arr[left++];
}
else {
result += m - left + 1;
dup[index++] = arr[right++];
}
}
while (left <= m) dup[index++] = arr[left++];
while (right <= e) dup[index++] = arr[right++];
for (int i = 0; i <= e - s; i++) {
arr[s + i] = dup[i];
}
return result;
}
long long merge_sort(int s, int e) {
long long result = 0;
if (s < e) {
int pivot = (s + e) / 2;
result += merge_sort(s, pivot);
result += merge_sort(pivot + 1, e);
result += partition(s, pivot, e);
}
return result;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) cin >> arr[i];
long long result = merge_sort(0,N-1);
cout << result;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 11047번 동전 0 (0) | 2020.01.17 |
|---|---|
| BOJ 10090번 Counting Inversions (0) | 2020.01.17 |
| BOJ 1992번 쿼드트리 (0) | 2020.01.17 |
| BOJ 1780번 종이의 개수 (0) | 2020.01.17 |
| BOJ 11728번 배열 합치기 (0) | 2020.01.17 |