[백준] 1517번 버블 소트 Java

문제 링크

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

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

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

출력

첫째 줄에 Swap 횟수를 출력한다

알고리즘: 정렬, 분할 정복

풀이

이 문제를 풀기 위해선 버블 정렬과 병합 정렬을 정확히 이해하고 있어야 한다.
버블 정렬은 O(n제곱) 이기 때문에 1초안에 수행할 수 없고,
병합 정렬은 O(n * log2n) 이기 때문에 n이 50만인 이 문제에 적합한 알고리즘이다.
(병합 할때 최대 left.length + right.length만큼 비교하고) n
(두 개로 분할하기 때문에 log2n번 수행한다.) log2n
-> 병합 과정에서 2개로 분할된 left와 right의 대소 비교를 통해서 swap을 카운팅 해줄 수 있다.

수가 left 수열에서 먼저 나온다면 count x
수가 right 수열에서 먼저 나온다면 count에 지금까지 나온 left 수열에 개수를 더해줌.
ex) left: 1 3, right: 2,4
1. 1과 2를 비교 1이 더 작음 -> left 수열에서 수가 나옴 cout = 0;
2. 3과 2를 비교 2가 더 작음 -> right 수열에서 수가 나옴 cout += 1;
3. 3과 4를 비교 3이 더 작음 -> left 수열에서 수가 나옴 cout = 1;
4. 4 하나 남았고 비교할 left 수열이 존재하지 않음 4 출력 cout = 1;
총 swap 횟수 1회

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static long sq[];
    static long swap = 0;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      sq = new long[N];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<N; i++) {
          sq[i] = Long.parseLong(st.nextToken());
      }
      merge_sort(sq);
      System.out.println(swap);
    }
    
    static long[] merge_sort(long p_sq[]) {
        if(p_sq.length == 1) return p_sq;
        else {
            //분할과정
            long left[] = new long[p_sq.length/2];
            long right[] = new long[p_sq.length - p_sq.length/2];
            left = merge_sort(Arrays.copyOfRange(p_sq, 0, p_sq.length/2));
            right = merge_sort(Arrays.copyOfRange(p_sq, p_sq.length/2, p_sq.length));
            //병합 과정
            int l_ind = 0;
            int r_ind = 0;
            int p_ind = 0;
            while(l_ind != left.length || r_ind != right.length) {
                if(left[l_ind] <= right[r_ind]) {
                    p_sq[p_ind] = left[l_ind];
                    l_ind += 1;
                } else {
                    p_sq[p_ind] = right[r_ind];
                    r_ind += 1;
                    swap += left.length - l_ind;
                }
                p_ind +=1;
                if(l_ind == left.length) {
                    for(int i=r_ind; i<right.length; i++) {
                        p_sq[p_ind] = right[i];
                        p_ind += 1;
                    }
                    r_ind = right.length;
                } else if(r_ind == right.length) {
                    for(int i=l_ind; i<left.length; i++) {
                        p_sq[p_ind] = left[i];
                        p_ind += 1;
                    }
                    l_ind = left.length;
                }
            }
            return p_sq;
        }
    }
}