백준 1517번 [버블 소트](C++)-yes6686- 티스토리

백준 문제 풀이: 1517 [버블 소트]

---

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

문제 설명:

버블 소트 알고리즘으로 주어진 배열을 정렬할 때, 몇 번의 swap이 발생하는지 계산하는 문제입니다. 단순히 O(n²)의 버블 소트를 구현하는 대신, 세그먼트 트리를 사용해 효율적으로 해결합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<pair<int, int>> arr;
int tree[2000001];

int init(int n, int s, int e) {
    if (s == e) {
        return tree[n] = 1;
    }
    return tree[n] = init(2 * n, s, (s + e) / 2) + init(2 * n + 1, (s + e) / 2 + 1, e);
}

int sum(int n, int s, int e, int l, int r) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return tree[n];
    return sum(2 * n, s, (s + e) / 2, l, r) + sum(2 * n + 1, (s + e) / 2 + 1, e, l, r);
}

void update(int n, int s, int e, int i, int v) {
    if (i < s || e < i) return;
    if (s == e) {
        tree[n] = v;
        return;
    }
    update(2 * n, s, (s + e) / 2, i, v);
    update(2 * n + 1, (s + e) / 2 + 1, e, i, v);
    tree[n] = tree[2 * n] + tree[2 * n + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        arr.push_back({x, i});
    }
    sort(arr.begin(), arr.end());
    init(1, 0, n - 1);

    long long int ans = 0;
    for (int i = 0; i < n; i++) {
        int k = arr[i].second;
        ans += sum(1, 0, n - 1, 0, k - 1); // Inversions count
        update(1, 0, n - 1, k, 0); // Mark as processed
    }
    cout << ans;
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 사용하여 효율적으로 inversion 개수를 계산합니다.
• 구현 세부사항:
  • init: 세그먼트 트리를 초기화하며 각 위치를 "사용 가능" 상태로 설정합니다.
  • sum: 특정 범위에서의 inversion 개수를 계산합니다.
  • update: 특정 위치를 "처리 완료" 상태로 업데이트합니다.
  • 배열을 정렬하여 값이 작은 순서대로 처리하며, 현재 인덱스보다 작은 인덱스에서의 값들을 세그먼트 트리를 통해 확인합니다.
• 시간 복잡도: O(n log n)
  • 정렬: O(n log n)
  • 세그먼트 트리 연산 (sum, update): O(log n)씩 n번 반복

---

결과

입력된 배열을 버블 소트를 통해 정렬하는 데 필요한 swap 횟수를 정확히 계산합니다. 세그먼트 트리를 사용하여 효율적으로 구현했으며, O(n²) 복잡도의 단순 버블 소트보다 훨씬 빠르게 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!