https://www.acmicpc.net/problem/1517

 

1517번: 버블 소트

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

www.acmicpc.net

문제는 버블 소트이지만 머지 소트를 이용하여 해결할 수 있습니다.

머지 소트 과정에서 뒤에있는 인덱스가 앞으로 올 때 이동한 만큼 더해주면 됩니다.

 

 

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

+ Recent posts

티스토리툴바