[백준] 1517 버블소트 java 쉬운 풀이

# 1. 문제 설명

[문제 설명](https://www.acmicpc.net/problem/1517)

# 2. 접근 방식

문제에서 주어진 데이터의 크기가 10^5이라서, 문제의 이름대로, bubble sort로 문제를 푼다면 시간 초과가 난다. 따라서 swap을 셀 수 있는 다른 방법을 생각해야 한다. 
병합정렬은 최악의 시간복잡도가 O(nlogn)으로 1억 번의 연산을 넘지 않아. 쓸만하다. 이제 병합 정렬의 어떤 움직임을 swap으로 간주할 것인지를 생각하면 된다. 



해당 그림은 merge_sort의 예시인데, merge sort 또한 투 포인터를 이용해 정렬을 하면서 swap이 일어난다. 위의 예시에서 53과 13을 보면, 53이 13 앞으로 간 것을 볼 수 있다.(1번의 swap) 또한 두 번째 merge 에서 53은 10과 43을 뛰어넘고 맨 오른쪽으로 간 것을 볼 수 있다. (두 번의 swap)

이처럼, **bubble_sort의 swap 총 횟수는 병합 정렬에서 원소가 이전 위치에서 얼마나 오른쪽으로 이동했는가?`를 전부 더한 것과 같다.**  이를 이용해 문제를 푼다.

# 3. 코드 분석

```java
import java.io.*;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static long cnt = 0;
    static Node [] arr;
    static Node [] tmp;
    public static void main(String[] args) throws IOException {
        // 1. 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new Node [N];
        tmp = new Node [N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = new Node(i, Integer.parseInt(st.nextToken()));
        }
        // 2. 계산
        merge_sort(0, N-1);
        System.out.println(cnt);
    }

    public static void merge_sort(int start, int end){
        // 0. 기저 조건
        if(end - start == 0) return;
        // 1. 분할 정복
        int mid = (start + end)/2;
        merge_sort(start, mid);
        merge_sort(mid+1, end);
        // 2. 계산 (투 포인터 활용)
        int s = start;
        int m = mid + 1;
        int k = start;

        for (int i = start; i <= end; i++) {
            tmp[i] = arr[i];
        }

        while (s <= mid && m <= end) {
           if(tmp[s].v <= tmp[m].v){
               arr[k] = tmp[s++];
           }else {
               arr[k] = tmp[m++];
           }
           if(k > arr[k].o_idx) cnt += (k - arr[k].o_idx);
           arr[k].o_idx = k;
           k++;
        }

        if(s<=mid){
            for (int i = s; i <= mid ; i++) {
                arr[k] = tmp[i];
                if(k> arr[k].o_idx) cnt += (k - arr[k].o_idx);
                arr[k].o_idx = k;
                k++;
            }
        }

        if(m<=end){
            for (int i = m; i <= end ; i++) {
                arr[k] = tmp[i];
                if(k> arr[k].o_idx) cnt += (k - arr[k].o_idx);
                arr[k].o_idx = k;
                k++;
            }
        }
    }
}

class Node {
    long o_idx;
    int v;

    public Node (long o_idx, int v){
        this.o_idx = o_idx;
        this.v = v;
    }
}
```

# 4. 성장 하기

내 풀이를 보면, Node라는 클래스를 따로 두고 o_idx를 나두어서 이전 index값을 저장해두었다. 하지만 merge sort는 분할 정복을 통해 병합 되는 과정이 계층적으로 일어나고 있기에, s, m 이라는 포인터가 `이전 index`, k가 `현재 들어갈 index` 인 점을 이용해서 문제를 풀 수도 있을 것 같다.