백준 3006: 터보소트

문제 요약

터보소트는 1부터 N까지 총 N개의 수가 섞여있을 때만 사용할 수 있으며, 다음과 같이 N단계로 이루어져 있다.

정리하면, 홀수번째 단계이면, 아직까지 고르지 않은 숫자 중 제일 작은 수를 고른 다음에, 그것을 인접한 숫자와 위치를 바꾸면서 올바른 위치로 이동시키고, 짝수번째 단계일때는, 제일 큰 수를 고른 다음에 위치를 이동시키는 것이다.

명우는 이때, 각 단계에서 숫자의 위치를 몇 번 바꾸는지 구하려고 한다.

1부터 N까지 총 N개의 수로 이루어진 배열이 주어졌을 때, 터보 소트의 각 단계에서, 숫자의 위치를 몇 번씩 바꾸는지 출력하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 세그먼트 트리

문제 풀이

현재 정렬 순서에 대해 위치를 몇 번 바꾸는지 구하는 문제이다. 세그먼트 트리로 구현했다.
터보 정렬 알고리즘을 살펴보면, 결국 현재 탐색중인 원소의 인덱스와 그 원소가 가야할 인덱스, 즉 그 거리를 구하는 것이 관건이다. 초기에 모든 리프노드들은 1의 값을 가진다. 이는 각 노드가 교체될 예정이라는 의미이다. 이를 통해 각 범위의 거리를 계산할 수 있다.
입력의 모든 값은 1이 아닌 0부터 숫자를 셈하였다.
우선 배열 ary를 선언하여 배열을 입력받을 때에 그 배열을 저장하는 것이 아니라, 해당 원소의 위치를 저장한다. 이는 어떠한 원소의 위치를 O(1)로 접근하기 위함이다.
그리고 0번 부터 알고리즘을 수행하는데, 처음으로는 0이 첫 번째 위치, 즉 0번 인덱스로 가야할 것이다. 이에 ary[0]으로 현재 0의 위치를 찾고, 그 위치의 세그먼트 트리의 리프 노드를 0으로 수정한 뒤, 0~해당 위치까지의 합을 구하여 그 거리를 구할 수 있다. 다음 차례도 같은 방식으로 구해준다.

즉, 어떠한 구간 사이의 거리를 구하는데, 그 거리가 변경 가능한 경우이므로 세그먼트 트리로 해결하는 문제였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int seg[400000], ary[100000];

int construct(int l, int r, int idx)
{
	if (l == r) seg[idx] = 1;
	else {
		int mid = (l + r) / 2;
		seg[idx] = construct(l, mid, idx * 2 + 1) + construct(mid + 1, r, idx * 2 + 2);
	}
	return seg[idx];
}

int update(int l, int r, int idx, int loc)
{
	if (loc < l || loc > r) return seg[idx];
	if (l == r) {
		if (l == loc) seg[idx] = 0;
	}
	else {
		int mid = (l + r) / 2;
		seg[idx] = update(l, mid, idx * 2 + 1, loc) + update(mid + 1, r, idx * 2 + 2, loc);
	}
	return seg[idx];
}

int sum(int start, int end, int l, int r, int idx)
{
	if (r < start || l > end) return 0;
	if (start <= l && r <= end) return seg[idx];
	int mid = (l + r) / 2;
	return sum(start, end, l, mid, idx * 2 + 1) + sum(start, end, mid + 1, r, idx * 2 + 2);
}

int main()
{
	int n, in, loc, num;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		ary[in - 1] = i;
	}
	construct(0, n - 1, 0);
	for (int i = 0; i < n; i++) {
		if (i % 2) {
			num = n - (i / 2) - 1;
			loc = ary[num];
			update(0, n - 1, 0, loc);
			printf("%d\n", sum(loc, n - 1, 0, n - 1, 0));
		}
		else {
			num = i / 2;
			loc = ary[num];
			update(0, n - 1, 0, loc);
			printf("%d\n", sum(0, loc, 0, n - 1, 0));
		}
	}
	return 0;
}