[백준] 1517 버블 소트 - C++

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

---

본격적인 설명 전, 하나의 간단한 개념을 짚고 넘어가면 좋다.

역전쌍(inversion)이란, 어떤 배열 내에서 자신보다 작은 인덱스를 가지지만 (자신보다 앞에 있지만)

자신보다 큰 값을 가지는 원소 쌍을 말한다.

 

다시 본론으로 돌아오자.

수열을 주고, 해당 수열로 버블소트를 수행할 때 Swap이 몇번 일어나는지 구하면 된다.

물론 진짜 버블소트를 돌리면 시간초과가 난다.

 

버블소트 수행 중 Swap이 일어난다는 뜻은 무엇인가?

Swap을 당하는 두 원소가 역전쌍임을 의미한다.

(버블소트 자체가 역전쌍을 올바른 순서로 뒤집는 것이기 때문)

그렇다면 우리는 배열에 대해 직접 버블소트를 수행하는게 아니라,

배열 내의 모든 역전쌍의 갯수를 구하면 된다.

 

Counting Inversions.. 세그먼트 트리를 이용하는 대표적인 문제이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int INF = 2e9;
ll ans = 0;
ll tree[500'000 * 4 + 16];
void update(ll left, ll right, ll idx, ll cidx, ll cval) {
	if (cidx < left || right < cidx) {
		return;
	}
	if (left == right) {
		tree[idx] = cval;
		return;
	}
	ll mid = (left + right) / 2;
	update(left, mid, idx * 2, cidx, cval);
	update(mid + 1, right, idx * 2 + 1, cidx, cval);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
	return;
}
ll query(ll left, ll right, ll idx, ll st, ll ed) {
	if (ed < left || right < st) {
		return 0;
	}
	if (st <= left && right <= ed) {
		return tree[idx];
	}
	ll mid = (left + right) / 2;
	return query(left, mid, idx * 2, st, ed) + query(mid + 1, right, idx * 2 + 1, st, ed);
}
int main() {
	ll n;
	cin >> n;
	vector<pair<ll, ll>> v; //val, idx
	v.push_back({ -INF, -1 });
	for (int i = 1; i <= n; i++) { //<1>
		ll x;
		cin >> x;
		v.push_back({x, i});
	}
	sort(v.begin()+1, v.end()); //<2>
	ll pre = INF;
	ll cnt = 0;
	for (int i = 1; i <= n; i++) { //<3>
		if (v[i].first != pre) cnt++;
		pre = v[i].first;
		v[i].first= cnt;
	}
	sort(v.begin()+1, v.end(), [](auto a, auto b) { //<4>
		return a.second < b.second;
		});
	for (int i = 1; i <= n; i++) { //<5>
		ans += query(1, n, 1, v[i].first+1, cnt);//<5-1>
		update(1, n, 1, v[i].first, 1);//<5-2>
	}
	cout << ans;
	return 0;
}

 

세그먼트 트리 구현에 관한 내용은 다른 블로그에서 찾아보자.. (필력 부족)

일단 우리가 사용할 세그트리 구조는 합세그이다.

쿼리와 업데이트 함수를 보면 인자 순서가 상당히 헷갈린다.

업데이트 함수는 (left, right, idx, cidx, cval)이고,

쿼리 함수는 (left, right, idx, st, ed)이다.

---

코드 설명

<1> : 무난하게 입력을 받는다. 나중에 써야 하니까 인덱스도 저장해준다 ({val, idx} 꼴)

 

<2> : 값 기준으로 정렬을 한다. 좌표압축을 하기 위함이다.

 

<3> : 중복인 값은 같은 번호를 갖도록 좌표압축 한다.(<1>의 val 부분에 저장) 번호의 범위는 [1, cnt] 가 된다.

 

<4> : 원본 배열의 인덱스 기준으로 정렬해서 입력 순서를 복원한다. 이 때문에 <1>에서 인덱스를 저장했다.

 

<5> : 배열의 왼쪽부터 값을 하나 뽑아 쿼리와 업데이트를 수행한다. 임의의 원소 X를 뽑은 시점에, 세그트리에는 X보다 인덱스가 작은 원소들에 대한 값만 저장되어 있다. (=자신보다 앞의 원소만 저장 되어있다. (어찌 생각해보면 당연하다))

 

<5-1> : 세그트리에 저장 되어있는 값(=자신보다 앞의 원소) 중, v[i].first (=자신의 번호) +1 부터 cnt까지의 범위의 구간합을 구한다.

이 설명만 들으면 여러 궁금증이 생길 수 있다.

세그트리 내에는 정확히 어떤 형태의 값이 들어가는지, 왜 저 범위 내에서 구간합을 구하는지 등...

이 질문들에 대한 답은 바로 다음에 오는 코드에 있다.

 

<5-2> : 자신의 값 (=좌표압축 된 값 =번호) 을 인덱스로서, 세그트리의 해당 위치에 1을 더한다.

라는 내용의 해당 코드로 인해, <5-1>에서 생긴 질문이 해결된다. (해결이 안된다면 댓글로..)

 

Q1. 세그트리 내에는 어떤 형태의 값이 들어가는가?

A. 좌표압축된 값(=자신의 번호)을 인덱스로서, 해당 값이 앞에서 몇번 나왔는지 들어가게 된다.

 

Q2. 왜 저 범위 (자신의 번호+1 ~ cnt) 내에서 구간합을 구하는가?

A. 쿼리를 수행하는 당시에는, 자신보다 앞에서 나온 원소들이 세그트리에 저장되어있다.

그 중 자신보다 큰 값, 즉 역전쌍을 이루는 값을 세야 한다.

좌표압축에서 값이 클수록 번호가 크므로, 자신보다 큰 값은 자신의 번호+1 ~ cnt(=번호 최댓값)에 대응된다.

따라서 이 구간의 합을 구하면 자신보다 앞에 있으면서 큰 값(역전쌍)의 갯수를 셀 수 있다.

---

---

버블소트 (근데 세그트리를 곁들인) (막상 버블소트는 안하는)

 

전형적인 Counting Inversions 문제이기에,

저 코드만으로 딸깍하며 풀 수 있는 문제가 꽤 있다... (안알랴줌)

---