[Jungol] 정올 1148 최종 울트라-퀵 소트

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=428&sca=60

Approach

합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

문제 내용에서 "인접한 두 수를 서로 바꿔서 주어진 수열을 오름차순으로 정렬" 한다고 해서

단순하게 버블 정렬의 원소 교환횟수를 묻는 문제로 생각해서 안됩니다.

 

arr = {1, 3, 4, 5, 2}를 선택 정렬을 할 때, 두번째로 작은 원소 『2』를 두번째 위치에 옮겨야 하지만

이 과정을 아래와 같이 수행한 결과라고 문제에서 정의합니다.

① swap(5, 2) → {1, 3, 4, 2, 5}

② swap(4, 2) → {1, 3, 2, 4, 5}

③ swap(3, 2) → {1, 2, 3, 4, 5}

▶ 총 3번의 교환횟수 발생

 

결과적으로 원소의 개수가 최대 500,000개 이므로 

병합정렬을 수행함에 있어서 교환횟수가 몇 번 필요한지 요구하는 문제입니다.

※ 퀵 소트의 경우 평균속도가 병합정렬과 비슷하지만, 원소의 배치에 따라 편차가 크기때문에 안전하지 않습니다.

그리고 이번 문제에서 요구하는 Test Case의 output 형태를 만족하지 않음

 

Merge 과정에서 오른쪽 그룹에서 수를 가져올 때, 이동되는 칸의 개수가 교환횟수 포함됩니다.

(왼쪽 그룹에 있는 원소의 경우 자리교환없이 merge된다고 볼 수 있습니다.)

→ 원소 『3』이 3번째 위치에 가기 위해서 세번의 자리이동(swap)이 필요합니다.

    (제출 코드) i = 1, mid = 3이므로,

    교환횟수 = mid - i + 1 = 3 - 1 + 1 = 3 으로 수치 계산

 

→ 원소 『6』은 2번 교환 발생.

---

#include <stdio.h>
#define LM 500005
 
typedef long long ll;
int N, arr[LM], copyArr[LM];
ll ans;
 
void input() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", arr + i);
    }
}
 
void ultraSort(int* arr, int start, int end) {
    // 0. base condition
    if (start >= end) return;
 
    // 1. divide
    int mid = (start + end) / 2;
 
    // 2. conquer
    ultraSort(arr, start, mid);
    ultraSort(arr, mid + 1, end);
 
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) copyArr[k++] = arr[i++];
        else {
            copyArr[k++] = arr[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) copyArr[k++] = arr[i++];
    while (j <= end) copyArr[k++] = arr[j++];
 
    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = copyArr[i];
    }
}
 
int main() {
    input();
    ultraSort(arr, 0, N - 1);
    printf("%lld\n", ans);
    return 0;
}