[P5] 백준 1517번 버블 소트 C++ 세그먼트 트리

리뷰

 

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

누적합 세그먼트 트리를 통해 버블 소트 시 swap의 횟수를 구하는 문제

 

 

전역 변수

• N : n의 최대값을 저장하기 위한 정수형 상수 변수
• n : 수열의 길이를 저장하기 위한 정수형 변수
• lst : 원소의 값과 인덱스를 저장하기 위한 pair<int, int>타입의 벡터
• tree : 세그먼트 트리 정보를 저장하기 위한 정수형 배열
• ans : 정답을 저장하고 출력하기 위한 정수형 변수

 

함수

1. update

void update(int node, int s, int e, int idx)

 

세그먼트 트리 정보를 업데이트 하기 위한 함수

1. 매개 변수로 현재 노드 정보 node, 탐색 범위 s, e, 업데이트할 인덱스 idx를 전달받는다.
2. 리프 노드에 도달했을 경우 현재 노드의 값을 1만큼 증가시킨다.
3. 리프 노드가 아닐 경우 현재 탐색 범위의 절반 값인 mid를 초기화 해준다.
4. idx가 mid보다 작거나 같을 경우 왼쪽 자식 노드로 재귀를 진행해 준다.
5. idx가 mid보다 클 경우 오른쪽 자식 노드로 재귀를 진행해 준다.
6. 재귀를 빠져나오면서 현재 노드의 값을 좌, 우 자식 노드의 값의 합으로 저장해 준다.

 

2. query

ll query(int node, int s, int e, int L, int R)

 

세그먼트 트리 노드를 통해 구간합 정보를 리턴받기 위한 함수

1. 매개 변수로 현재 노드 정보 node, 탐색 범위 s, e, 구간합을 구할 범위 L, R을 전달받는다.
2. 첫 번째 기저조건으로 만약 L혹은 R이 구간을 벗어난 경우 0을 리턴해 준다.
3. 두 번째 기저조건으로 만약 현재 탐색 범위가 L, R 범위와 겹칠 경우 현재 노드에 저장된 값을 리턴해 준다.
4. 기저 조건에 해당되지 않을 경우 현재 탐색 범위의 절반 값인 mid를 초기화 해준다.
5. 좌, 우 자식 노드로 재귀를 진행하고, 전달 받은 리턴값을 각각 left, right에 저장한다.
6. left와 right를 더한 값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, lst의 크기를 n으로 resize해준다.
2. n개의 원소 정보를 입력 받아 각각의 값을 lst의 첫번째 값으로 저장해 주고, 인덱스는 두번째 값으로 저장해 준다.
3. sort 함수를 통해 lst를 오름차순으로 정렬해 준다.
4. 다시 n개의 요소를 순회하며 ans에 i에서 0 ~ 현재 원소의 인덱스 까지의 구간합을 뺀 값을 더해준다.
5. 이후 update 함수를 통해 세그먼트 트리에 현재 원소의 인덱스인 리프 노드에 값을 1만큼 증가시켜 준다.
6. 탐색을 모두 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 문제 자체가 어려운 문제였다, 세그먼트 트리는 응용 할 수 있는 방법이 정말 무궁무진 한 것 같다.

 

참고 사항

 

• 작은 숫자부터 처리하면서, 각 숫자의 왼쪽에 이미 처리된 숫자가 몇 개 있는지를 확인하고, 현재까지 처리한 전체 숫자 개수에서 그 값을 빼면 현재 숫자보다 작은데 뒤에 있는 숫자들의 개수를 알 수 있다.
• 세그먼트 트리는 단순히 "어떤 위치에 숫자가 있는지"를 표시하고, 특정 구간에 숫자가 몇 개 있는지를 빠르게 계산하는 데 사용된다.
• 최악의 경우 ans는 5 * 1e5 * (5 * 1e5 - 1) / 2로 long long타입을 사용해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 500000;
int n;
vector<pair<int, int>> lst;
ll tree[N * 4];
ll ans;

void update(int node, int s, int e, int idx) {
	if (s == e) tree[node]++;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

ll query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	ll left = query(node * 2, s, mid, L, R);
	ll right = query(node * 2 + 1, mid + 1, e, L, R);
	return left + right;
}

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

	cin >> n;
	lst.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> lst[i].first;
		lst[i].second = i;
	}
	sort(lst.begin(), lst.end());

	for (int i = 0; i < n; ++i) {
		ans += i - query(1, 0, n - 1, 0, lst[i].second);
		update(1, 0, n - 1, lst[i].second);
	}
	cout << ans;
}