https://www.acmicpc.net/problem/1517
문제는 버블 소트이지만 머지 소트를 이용하여 해결할 수 있습니다.
머지 소트 과정에서 뒤에있는 인덱스가 앞으로 올 때 이동한 만큼 더해주면 됩니다.
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int list[], sorted[]; static int N; static long ans; static void mergesort(int l, int m, int r) { int i = l; int k = l; int j = m + 1; while (i <= m && j <= r) { if (list[i] <= list[j]) { sorted[k] = list[i]; i++; } else { if (list[k] != list[j]) ans += (j - k); sorted[k] = list[j]; j++; } k++; } if (i > m) { for (; j <= r; j++, k++) { sorted[k] = list[j]; } } else { for (; i <= m; i++, k++) { sorted[k] = list[i]; } } for (int t = l; t <= r; t++) { list[t] = sorted[t]; } } static void merge(int l, int r) { if (l != r) { int m = (l + r) / 2; merge(l, m); merge(m + 1, r); mergesort(l, m, r); } } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); list = new int[N]; sorted = new int[N]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { list[i] = Integer.parseInt(st.nextToken()); } } public static void main(String[] args) throws Exception { input(); merge(0, N - 1); System.out.println(ans); } } | cs |
'algorithm > data-structure' 카테고리의 다른 글
boj 5639 이진 검색 트리 (0) | 2021.01.24 |
---|---|
boj 1991 트리 순회 (0) | 2021.01.22 |
boj 11003 최솟값 찾기 (0) | 2021.01.22 |
boj 2517 달리기 (0) | 2021.01.22 |
boj 3425 고스택 (0) | 2021.01.22 |