백준 3006 터보소트 (c++) : 피너

3006번: 터보소트

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

 

세그먼트 트리를 이용해서 풀었다.

 

7
5 4 3 7 1 2 6

위와 같이 주어졌다고 하자

 

정렬하는 순서는 1, 7, 2, 6, 3, 5, 4 이다.

여기서 알수있는것은 3을 정렬하기 전에 1과 2는 무조건 정렬이 되어있다는 것이다.

또 5를 정렬하기 전에는 7, 6은 무조건 정렬이 되어 있다.

 

이걸 더 발전시켜보자

7
1 5 4 3 2 6 7

위에서 1과 7을 정렬한 형태이다. 1과 7은 맨 끝놈들이니 간단하게 생각하면 된다.

이제 2를 옮긴다고 생각해보자

 

2를 옮기기 전에 1은 무조건 앞에 있는 상태이다. 

2 9 8 7 6 5 4 3 1

 

위와 같은 상황이었다면 1이 앞으로 이동하고 나면 2의 자리가 뒤로 밀리게 될 것이다.

1 2 9 8 7 6 5 4 3

위에 처럼 말이다. 

 

하지만

1 2 9 8 7 6 5 4 3

처음부터 이 상황이었다면 2의 위치에는 아무런 변화가 없다.

 

여기서 공식을 하나 생각할수있다.

2의 위치 = 처음 2의 위치 + 2보다 작은 숫자중 2보다 뒤에 있는 숫자들의 수

 

근데 또다시 생각해보면

9 2 8 7 6 5 4 3 1

위에에서 1이 이동해

1 9 2 8 7 6 5 4 3

위 처럼 되고 이제 9가 이동해서

1 2 8 7 6 5 4 3 9

위 처럼 된다.

이제 공식에 한가지를 추가할수있다.

2의 위치 = 처음 2의 위치 + 2보다 작은 숫자중 2보다 뒤에 있는 숫자들의 수

원래 공식에서

2의 위치 = 
처음 2의 위치 + 2보다 작은 숫자중 2보다 뒤에 있는 숫자들의 수 - 2보다 큰 숫자중 2보다 앞에 있는 숫자들의 수

이렇게 추가할수있다.

 

위의 공식은 오른쪽에서 왼쪽으로 옮길때 사용하는 공식이다.

왼쪽에서 오른쪽으로 옮길때는 약간 변형한 공식을 사용하면 된다.

 

int n;
int arr[100001];
int segtree_L2R[4 * 100001];
int segtree_R2L[4 * 100001];

사용할 변수들이다.

segtree_L2R은 왼쪽에서 오른쪽으로 이동시킨 놈들이고 segtree_R2L은 그 반대이다.

void update_L2R(int node, int start, int end, int left, int right, int idx, int val) {
	if (end < left || right < start) return;
	if (start == end) {
		if (start == left) segtree_L2R[node] = val;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) update_L2R(node * 2, start, mid, left, right, idx, val);
	else update_L2R(node * 2 + 1, mid + 1, end, left, right, idx, val);

	segtree_L2R[node] = segtree_L2R[node * 2] + segtree_L2R[node * 2 + 1];
}

void update_R2L(int node, int start, int end, int left, int right, int idx, int val) {
	if (end < left || right < start) return;
	if (start == end) {
		if (start == left) segtree_R2L[node] = val;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) update_R2L(node * 2, start, mid, left, right, idx, val);
	else update_R2L(node * 2 + 1, mid + 1, end, left, right, idx, val);

	segtree_R2L[node] = segtree_R2L[node * 2] + segtree_R2L[node * 2 + 1];
}

세그먼트 트리 업데이트 함수이다.

int query_L2R(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return segtree_L2R[node];

	int mid = (start + end) / 2;
	return query_L2R(node * 2, start, mid, left, right) + query_L2R(node * 2 + 1, mid + 1, end, left, right);
}

int query_R2L(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return segtree_R2L[node];

	int mid = (start + end) / 2;
	return query_R2L(node * 2, start, mid, left, right) + query_R2L(node * 2 + 1, mid + 1, end, left, right);
}

세그먼트 트리에서 구간합을 구하는 함수이다.

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		arr[a] = i;
	}

입력을 받아준다.

i가 1일때 2가 입력으로 들어오면 arr[2] = 1을 통해 2가 현재 1의 자리에 있다는 걸 알수있다.

	for (int left = 1, right = n; left <= right; left++, right--) {
		cout << solve(left, 0) << '\n';
		if (left != right) cout << solve(right, 1) << '\n';
	}

그 다음에는 왔다갔다 하면서 풀어주면 된다.

int solve(int idx, int lr) {
	if (lr == 0) {
		int now = arr[idx] + query_R2L(1, 1, n, arr[idx], n) - query_L2R(1, 1, n, 1, arr[idx]);
		int target = idx;
		update_R2L(1, 1, n, arr[idx], arr[idx], arr[idx], 1);
		return abs(target - now);
	}
	else {
		int now = arr[idx] - query_L2R(1, 1, n, 1, arr[idx]) + query_R2L(1, 1, n, arr[idx], n);
		int target = idx;
		update_L2R(1, 1, n, arr[idx], arr[idx], arr[idx], 1);
		return abs(target - now);
	}
}

solve 함수이다.

int solve(int idx, int lr) {
	if (lr == 0) {
		int now = arr[idx] + query_R2L(1, 1, n, arr[idx], n) - query_L2R(1, 1, n, 1, arr[idx]);
		int target = idx;
		update_R2L(1, 1, n, arr[idx], arr[idx], arr[idx], 1);
		return abs(target - now);
	}

lr이 0이면 오른쪽에서 왼쪽으로 옮긴다는 이야기이다. 즉, 1, 2, 3, 4... 이런 숫자란 의미다.

현재 위치 = 원래 위치 + 원래 위치 ~ n 사이에 오른쪽에서 왼쪽으로 옮겨진 숫자들 - 1 ~ 원래위치 사이에 왼쪽에서 오른쪽으로 옮겨진 숫자들

target은 목표지점이다. idx가 2면 목표 지점은 2번이 된다.

거리는 간단하게 abs를 통해 구해주면 되고 그전에 원래 위치가 옮겨졌다는걸 세그먼트 트리를 이용해 업데이트해주낟.

오른쪽에서 왼쪽으로 옮겨진것이니 R2L을 사용했다.

	else {
		int now = arr[idx] - query_L2R(1, 1, n, 1, arr[idx]) + query_R2L(1, 1, n, arr[idx], n);
		int target = idx;
		update_L2R(1, 1, n, arr[idx], arr[idx], arr[idx], 1);
		return abs(target - now);
	}
}

그 반대도 마찬가지이다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int arr[100001];
int segtree_L2R[4 * 100001];
int segtree_R2L[4 * 100001];

void update_L2R(int node, int start, int end, int left, int right, int idx, int val) {
	if (end < left || right < start) return;
	if (start == end) {
		if (start == left) segtree_L2R[node] = val;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) update_L2R(node * 2, start, mid, left, right, idx, val);
	else update_L2R(node * 2 + 1, mid + 1, end, left, right, idx, val);

	segtree_L2R[node] = segtree_L2R[node * 2] + segtree_L2R[node * 2 + 1];
}

void update_R2L(int node, int start, int end, int left, int right, int idx, int val) {
	if (end < left || right < start) return;
	if (start == end) {
		if (start == left) segtree_R2L[node] = val;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) update_R2L(node * 2, start, mid, left, right, idx, val);
	else update_R2L(node * 2 + 1, mid + 1, end, left, right, idx, val);

	segtree_R2L[node] = segtree_R2L[node * 2] + segtree_R2L[node * 2 + 1];
}

int query_L2R(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return segtree_L2R[node];

	int mid = (start + end) / 2;
	return query_L2R(node * 2, start, mid, left, right) + query_L2R(node * 2 + 1, mid + 1, end, left, right);
}

int query_R2L(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return segtree_R2L[node];

	int mid = (start + end) / 2;
	return query_R2L(node * 2, start, mid, left, right) + query_R2L(node * 2 + 1, mid + 1, end, left, right);
}

int solve(int idx, int lr) {
	if (lr == 0) {
		int now = arr[idx] + query_R2L(1, 1, n, arr[idx], n) - query_L2R(1, 1, n, 1, arr[idx]);
		int target = idx;
		update_R2L(1, 1, n, arr[idx], arr[idx], arr[idx], 1);
		return abs(target - now);
	}
	else {
		int now = arr[idx] - query_L2R(1, 1, n, 1, arr[idx]) + query_R2L(1, 1, n, arr[idx], n);
		int target = idx;
		update_L2R(1, 1, n, arr[idx], arr[idx], arr[idx], 1);
		return abs(target - now);
	}
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		arr[a] = i;
	}

	for (int left = 1, right = n; left <= right; left++, right--) {
		cout << solve(left, 0) << '\n';
		if (left != right) cout << solve(right, 1) << '\n';
	}

	return 0;
}

전체코드다.