[1517] 버블 소트

문제 링크 : https://www.acmicpc.net/problem/1517

1517 - 버블 소트

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	512MB

---

풀이

솔직히 얘기하면, 난 이 문제가 왜 세그먼트 트리로 풀리는지 확신이 들지 않는다. 사실 구간문제로 바꿀 수 있다는 것은 이해했고, 그래서 세그먼트 트리를 쓴다는 것은 알겠는데, 왜 이 문제가 구간문제로 바뀔 수 있는지를 모른다고 해야할까? 구현 아이디어보다는 문제 아이디어에 대한 이해가 아직 부족하다. 다르게 말하면 내가 아직 세그먼트 트리 문제를 보더라도 어떻게 풀어야하는지 모른다는 것을 의미할 것이다. 이 부분은 다른 문제를 더 보면서 연습이 필요할 것 같다.

이 문제를 해결하기 위한 아이디어는 2가지다.

• Swap을 실행하는 조건
• Swap이 실행되는 횟수를 빠르게 계산해야한다는 문제의 조건

버블소트에서 Swap이 발생하는 조건이 무엇일까? 버블소트의 코드를 보면 알 수 있다.

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n - 1; ++j) {
        if (arr[i] > arr[j]) {
            swap(i, j);
        }
    }
}

인접한 값에 대해서 “왼쪽이 오른쪽보다 값이 크다면” swap 연산이 실행된다. 그런데 그것이 한번 일어나는게 아니라, 연속적으로 일어난다. 생각해보면 어느 한 원소는 그 원소보다 왼쪽에 있으면서 자신보다 큰 원소에 대해서는 무조건 swap 연산이 일어나게 된다. 다른 원소들도 마찬가지. 또 그리고, 위 경우를 제외하고는 swap이 일어나지 않는다는 사실이 있다. 이 부분이 아직 내가 제대로 이해하지 못한 부분인데, 위 2가지 이유 때문에, 버블소트에서의 swap 횟수는 자신보다 왼쪽에 있으면서 자신보다 큰 원소들의 개수의 합이 된다는 것이다.

2번째 조건, swap 횟수를 빠르게 계산할 수 있는 방법이 뭐가 있을까? 일반적이라면 $O(N^2)$으로 전부 계산하는 방법이 있지만, 수가 50만개나 있기 때문에 시간상 불가능하다. 그럼 다른 방법이 무엇이 있을까?

아까 1번 조건에서, swap의 횟수는 각 원소에 대해서 자신보다 왼쪽에 있으면서 자신보다 큰 원소들의 개수를 구하고 그 합을 반환하는 것으로 계산할 수 있다고 하였다. 이것을 반대로 얘기하면 자신보다 오른쪽에 있으면서 자신보다 작은 원소들의 합이라고도 얘기할 수 있을 것이다. 그런데 그걸 어떻게 구할 수 있을까?

여기서 의외로 세그먼트 트리를 이용하여 계산할 수 있는 방법이 있다고 한다. 방법을 놓고 생각해보면 세그먼트 트리 + sparse array 정도가 되겠다. 아래와 같은 아이디어로 swap 횟수를 계산할 수 있다.

• 먼저 입력으로 주어진 배열을 index를 포함하여 정렬시킨다
• 각 원소에 대해 반복한다
  • 원소가 원래 있었던 자리를 찾는다 (정렬하기 전에 추가했던 index로 확인 가능)
  • 위치를 찾았다면, 그 위치보다 오른쪽에 있으면서 원소보다 작은 값들의 개수를 센다
  • 그 원소를 사용했다고 체크한다

그럼 오른쪽에 있으면서 원소보다 작은 값을 어떻게 셀 수 있을까? 여기서 우리는 세그먼트 트리를 이용하여 구간합을 구할 수 있다. 그 원소를 사용했다고 체크하는 것을, 세그먼트 트리의 리프노드의 값을 1로 하는 것이다. 그러면, 다른 원소가 개수를 셀 때, 자신보다 오른쪽에 있는 구간을 전부 탐색해보면 개수를 셀 수 있다는 것이다. 이미 사용한 값은 지금 내가 보고있는 값보다는 분명 작은 수이고, 그 수들은 리프노드가 1로 업데이트되어있기 때문이다. 즉, 오른쪽 구간에서 1로 켜져있는 것들의 개수를 구하면 된다는 것!

그러므로, 우리는 배열의 특정 값을 1로 업데이트하는것과, 특정 구간에서의 합을 구해야하므로 세그먼트 트리 문제로 생각할 수 있다는 것이다. 이런 생각은 어떻게 하는거지..

• 참고 알고리즘 : 세그먼트 트리

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 27

#include <stdio.h>

typedef long long ll;
typedef struct Node {
    int v;
    int i;
} ND;

#define MAX_IDX 500000
ND arr[MAX_IDX];
int n;
ll retval;

int tree[MAX_IDX * 4];
const int ROOT = 1;
const int SET = 1;

int cmp(ND* a, ND* b) {
    if (a->v == b->v) {
        return a->i > b->i;
    } else {
        return a->v > b->v;
    }
}

void update(int node, int s, int e, int t, int diff) {
    if (t < s || t > e) {
        return;
    }

    tree[node] += diff;
    if (s < e) {
        update(node * 2, s, (s + e) / 2, t, diff);
        update(node * 2 + 1, (s + e) / 2 + 1, e, t, diff);
    }
    return;
}

ll query(int node, int s, int e, int l, int r) {
    if (l > e || r < s) {
        return 0;
    }

    if (l <= s && e <= r) {
        return tree[node];
    }

    return query(node * 2, s, (s + e) / 2, l, r) + query(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        arr[i] = (ND){a, i};
    }

    qsort(arr, n, sizeof(ND), cmp);
    // init();

    for (int i = 0; i < n; ++i) {
        retval += query(ROOT, 0, n - 1, arr[i].i - 1, n - 1);
        update(ROOT, 0, n - 1, arr[i].i - 1, SET);
    }

    printf("%lld", retval);
    return 0;
}