[BOJ 3006] 터보소트(c++)

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

 

문제 개요

N개의 수를 정렬하는 터보소트를 구현해야 합니다. 터보소트는 다음과 같은 규칙으로 동작합니다.

• 홀수 단계: 남은 숫자 중 가장 작은 수를 찾아 앞쪽 올바른 위치로 이동
• 짝수 단계: 남은 숫자 중 가장 큰 수를 찾아 뒤쪽 올바른 위치로 이동

각 단계에서 인접한 원소와 swap하며 이동하는데, swap하는 횟수를 출력하는 문제입니다.

(1 <= N < 100,000)

둘째 줄부터 N개의 줄은 1보다 크거나 같고, N보다 작거나 같으며 중복된 수가 없습니다.

---

문제 풀이

각 단계에서 swap의 횟수는 타겟 숫자와 목표 위치 사이에 있는 아직 정렬되지 않은 수들의 개수입니다.

예를 들어, 숫자 3이 7번째 위치에 있고 맨 앞(3번째)으로 가야 하고, 7번째부터 목표 사이까지 아직 제거되지 않은 숫자가 3개 잇다면 swap의 수는 3번입니다.

 

이를 구현하기 위해서는 다음 연산들을 효율적으로 처리해야 합니다.

• 남은 숫자 중 최소/최대값 찾기
• 특정 구간에 남은 숫자 개수 세기
• 숫자 제거

이를 위해 최댓값과 최솟값을 처리하는 두 개의 세그먼트트리를 사용하였습니다.

class node {
public:
    int val;   // 해당 구간의 최솟값/최댓값
    int idx;   // 그 값의 위치
    int cnt;   // 구간에 남아있는 원소 개수
};

node mn_seg[100001];
node mx_seg[100001];

---

코드

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

const int mx = 1e9;
const int mn = -1;

class node {
public:
	int val, idx, cnt;
};

int n;
node mx_seg[100001 * 4];
node mn_seg[100001 * 4];
int arr[100001];

void init(int x, int s, int e) {
	if (s == e) {
		mx_seg[x] = { arr[s], s, 1 };
		mn_seg[x] = { arr[s], s, 1 };
		return;
	}
	int mid = s + (e - s) / 2;
	init(x * 2, s, mid);
	init(x * 2 + 1, mid + 1, e);
	if (mx_seg[x * 2].val > mx_seg[x * 2 + 1].val) {
		mx_seg[x] = { mx_seg[x * 2].val, mx_seg[x * 2].idx, mx_seg[x * 2].cnt + mx_seg[x * 2 + 1].cnt };
	}
	else {
		mx_seg[x] = { mx_seg[x * 2 + 1].val, mx_seg[x * 2 + 1].idx, mx_seg[x * 2].cnt + mx_seg[x * 2 + 1].cnt };
	}
	if (mn_seg[x * 2].val < mn_seg[x * 2 + 1].val) {
		mn_seg[x] = { mn_seg[x * 2].val, mn_seg[x * 2].idx, mn_seg[x * 2].cnt + mn_seg[x * 2 + 1].cnt };
	}
	else {
		mn_seg[x] = { mn_seg[x * 2 + 1].val, mn_seg[x * 2 + 1].idx, mn_seg[x * 2].cnt + mn_seg[x * 2 + 1].cnt };
	}
}

void update(int x, int s, int e, int v) {
	int mid = s + (e - s) / 2;
	if (s == e) {
		mx_seg[x] = { mn, s, 0 };
		mn_seg[x] = { mx, s, 0 };
		return;
	}

	mx_seg[x].cnt--;
	mn_seg[x].cnt--;

	if (mn_seg[x * 2].val <= v && v <= mx_seg[x * 2].val) {
		update(x * 2, s, mid, v);
	}
	else {
		update(x * 2 + 1, mid + 1, e, v);
	}

	node left = mx_seg[x * 2];
	node right = mx_seg[x * 2 + 1];
	if (left.val > right.val) {
		mx_seg[x] = { left.val, left.idx, left.cnt + right.cnt };
	}
	else {
		mx_seg[x] = { right.val, right.idx, left.cnt + right.cnt };
	}

	left = mn_seg[x * 2];
	right = mn_seg[x * 2 + 1];
	if (left.val < right.val) {
		mn_seg[x] = { left.val, left.idx, left.cnt + right.cnt };
	}
	else {
		mn_seg[x] = { right.val, right.idx, left.cnt + right.cnt };
	}
}

int mn_query(int x, int s, int e, int l, int r) {
	if (r < s || e < l) return 0;
	else if (l <= s && e <= r) {
		return mn_seg[x].cnt;
	}
	int mid = s + (e - s) / 2;
	return mn_query(x * 2, s, mid, l, r) + mn_query(x * 2 + 1, mid + 1, e, l, r);
}

int mx_query(int x, int s, int e, int l, int r) {
	if (r < s || e < l) return 0;
	else if (l <= s && e <= r) {
		return mx_seg[x].cnt;
	}
	int mid = s + (e - s) / 2;
	return mx_query(x * 2, s, mid, l, r) + mx_query(x * 2 + 1, mid + 1, e, l, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int l = 1, r = n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	init(1, 1, n);
	while (l <= r) {
		int l_cnt = mn_query(1, 1, n, 1, mn_seg[1].idx);
		cout << l_cnt - 1 << '\n';
		update(1, 1, n, l);
		if (l == r) break;
		int r_cnt = mx_query(1, 1, n, mx_seg[1].idx, n);
		cout << r_cnt - 1 << '\n';
		update(1, 1, n, r);
		l++, r--;
	}
	return 0;
}