[java 백준] plat 5/ 1517번 버블정렬

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

1517번: 버블 소트

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static long[] arr;
    public static long[] sorted;
 
    public static long cnt;
 
    // 분할
 
    public static void mergeSort(long arr[], int start, int end) {
        if (start < end) {
            int middle = (start + end) / 2;
            mergeSort(arr, start, middle);
            mergeSort(arr, middle + 1, end);
            merge(arr, start, middle, end);
        }
    }
 
    public static void merge(long[] arr, int start, int middle, int end) {
        int i = start;
        int j = middle + 1;
        int k = start;
 
        while (i <= middle && j <= end) {
            if (arr[i] <= arr[j]) {
                sorted[k] = arr[i];
                i++;
 
            } else {
                cnt += middle - i + 1;
                sorted[k] = arr[j];
                j++;
 
            }
            k++;
        }
 
        if (i > middle) {
            
            for (int t = j; t <= end; t++) {
                sorted[k] = arr[t];
                k++;
            }
        } else {
            
            for (int t = i; t <= middle; t++) {
                sorted[k] = arr[t];
                k++;
            }
        }
 
        for (int t = start; t <= end; t++) {
            arr[t] = sorted[t];
 
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        cnt = 0;
        arr = new long[n];
        sorted = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
 
        mergeSort(arr, 0, n - 1);
 
        System.out.println(cnt);
 
    }
 
}

 

우선 분할정복 관련 문제들만 풀고 있었기 때문에 당연히 나눠서 풀어야 한다는 생각이 들었다.

그래서 병합정렬을 쓰는게 nlogn의 시간복잡도를 가지니까 빠를거라 생각해서 구현했다.

 

특히 문제에서 인접해 있는 두 수 중에서 앞에 있는 수가 뒤에 있는 수보다 크면 swap되면서 횟수가 1만큼 증가하는데

병합정렬에서 

 while (i <= middle && j <= end) {

            if (arr[i] > arr[j]) {

                sorted[k] = arr[j];

                i++;

}

}

 

--> 노란색 부분이 swap을 의미하기 때문에 병합 정렬을 써주었다. 

 

 

문제를 풀면서 잘못 생각한 부분

 

if (i > middle) {

            

            for (int t = j; t <= end; t++) {

                sorted[k] = arr[t];

                k++;

 

            }

        }

--> 이 부분에서 for문을 쓰지 않고 한번더 mergeSort를 호출해서 재귀를 쓰니까 시간초과에 걸렸다. 재귀를 쓴 이유는 애초에 arr이 정렬되어 있는 상태가 아니여서 끝까지 정렬해주고 -> sorted에 넣어주기 위해 재귀를 썼는데  출력해보니까 굳이 그렇게 하지 않아도 결국에 sorted는 잘 정렬되어서 나왔다.

 

이렇게 재귀가 안되면 결국엔 cnt에 1만 더해주는게 아닌  swap된 횟수를 구체적으로 더해주는 것이 핵심이라고 생각했다. (여기서 부터는 잘 모르겠어서 다른 사람들 코드를 봤다..!)

 

예를 들어 2 3 4 1 5 라는 배열이 있다. 

이걸 분할하면 (2 3 4 ) (1 5) 로 분할할 수 있다. 예를 다시 병합 해주면

 

i가 2를 가리키고 j가 1을 가리키게 된다. arr[i]<=arr[j] 이므로 sorted[0]=arr[j]이고 arr[j]는 1이기에 sorted[0]은 1이 된다. 그러면 1은 사실상 2,3,4 <-- 3개를 앞지르고 0번째 인덱스에 간거기 때문에 총 3번 swap된걸로 생각할 수 있다.

 

이걸 발문에서 주어진 예시 처럼 인접 숫자들 끼리 바꾸는걸로 구현하면

 

원래배열 : 2 3 4 1 5

 

1번째 swap: 2 3 1 4 5 --> 1이 4 앞지름

2번째 swap: 2 1 3 4 5 --> 1이 3 앞지름

3번째 swap: 1 2 3 4 5--> 1이 2 앞지름 

 

이렇게 앞 지른걸 swap으로 생각해주면 cnt+=mid-i+1 이라는 식을 도출해낼 수 있다.

 

정리하자면

 

j포인터에 있는 애가 i 포인터에 있는 애보다 작을 경우 인접한 두 숫자 중 뒤에꺼가 더 작은거와 같은 경우가 된다.

그러면 swap을 해줘야 하는데 이는 sorted 배열에서 앞 지른 횟수와 같다고 볼 수 있다.

 

 

 

 

참고 사이트

이건 swap찾아보다가 최소 swap횟수에 대한 글을 봤는데 나중에 이거랑 관련된 문제 풀 수도 있을 것 같아서 첨부해둔다.

https://hub1234.tistory.com/23

[HakerRank]Minimum Swaps2_배열 정렬에 필요한 최소 스왑 횟수 구하기

 

예를 들어 배열이 2 3 4 1 5가 있다면

arr[2-1]=2

arr[3-1]=3

arr[4-1]=4

arr[1-1]=1

arr[5-1]=5

이런식으로 숫자를 입력받고 arr에 저장한다.

그러면 바로 arr상에서 1 2 3 4 5 로 정렬되는 것을 확인할 수 있다. 

 

아무튼 플레티넘 단계 문제라서 그런가.. 막상 구현하면 할 수 있을 것 같은데 생각해내는게 어렵다. 갈길이 멀다.. ㅜㅜ