[BOJ] 버블소트 백준 1517, 2751 (자바 JAVA) - 병합정렬

📌 병합정렬

분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘

시간 복잡도 평균값은 O(nlogn)

 

출처: 구글

🔒 버블소트 - 백준 1517

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 횟수를 출력한다

🔑 핵심 아이디어

• N의 범위가 1,000,000,000 이므로 버블소트가 아닌 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 사용해야 한다.
• 두 그룹을 병합 하는 과정에서 swap이 일어나는데, 오른쪽 요소 값이 왼쪽보다 클 때 index가 이동한 거리를 계산해서 result에 추가하면 된다. (병합 정렬 코드와 거의 같음)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static int[] arr, tmp;
    public static long result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        tmp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        mergeSort(0, N-1);

        System.out.println(result);
    }
    
    public static void mergeSort(int start, int end){
        if(start >= end) return;
        int mid = (start + end)/2;
        mergeSort(start, mid);
        mergeSort(mid+1, end);

        int L = start;
        int R = mid + 1;
        int point = start;

        while(L <= mid || R <= end){
            if(R > end||(L <= mid && arr[L] <= arr[R])){
                tmp[point++] = arr[L++];
            }
            else{ // L > mid || R <= end && arr[L] > arr[R]
                if(L <= mid && arr[L] > arr[R] && R <= end){ // 오른쪽 값이 작은 경우
                    result += R - point; // 추월한 인덱스만큼 result에 추가
                }
                tmp[point++] = arr[R++];
            }
        }
        for (int i = start; i < end + 1; i++) {
            arr[i] = tmp[i];
        }
    }
}

 

아래 병합 정렬 코드에서 result 부분만 추가해준 것

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static int[] arr, tmp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        tmp = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(0, N-1);
        StringBuilder sb = new StringBuilder();
        for (int i : arr) {
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
    
    public static void mergeSort(int start, int end){
        if(start >= end) return;
        int mid = (start + end)/2;
        mergeSort(start, mid);
        mergeSort(mid+1, end);

        int L = start;
        int R = mid + 1;
        int point = start;

        while(L <= mid || R <= end){
            // 오른쪽이 이미 정렬된 경우 왼쪽 요소를 순차적으로 뒤에 저장
            // 양쪽에 요소가 남아 있으며 왼쪽이 오른쪽보다 작을 때 왼쪽 요소 저장
            if(R > end||(L <= mid && arr[L] <= arr[R])){
                tmp[point++] = arr[L++];
            }
            // L > mid || R<=end && arr[L] > arr[R]
            else{
                tmp[point++] = arr[R++];
            }
        }
        for (int i = start; i < end + 1; i++) {
            arr[i] = tmp[i];
        }
    }
}

 

 

코테 정리 깃허브 링크

GitHub - Suyoung225/JavaPrac: Java로 백준, 프로그래머스 알고리즘 문제 풀이