백준 2832번 정렬

문제

상근이는 다음과 같은 정렬 알고리즘을 만들었다.

reverse-sort(sequence a)
    while (A is not in nondecreasing order)
        partition a into the minimum number of slopes
        for every slope with length greater than one
            reverse(slope)

여기서 slope란 감소하는 a의 연속 부분 수열이다. reverse는 그 구간의 순서를 뒤집는다.

1부터 N으로 이루어진 길이가 N인 순열이 주어진다. 처음에 순열의 slope의 길이는 모두 짝수이다. reverse를 몇 번 호출하는지 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : 투포인터, fenwick tree

(0) 생각

 생각해보면 주어진 정렬 알고리즘은 다음과 같이 작동하게 됩니다. 

    1. 수열의 내림차순인 부분 수열을 뒤집어 오름차순으로 만들고

    2. 두 개씩 잡아서 뒤집습니다.

 

 예를 들어 다음과 같은 수열이 있다고 생각해봅시다.

수열							호출 회수
6	5	3	2	7	4	1	0

 일단 생각 1.에 따라 내림차순인 부분수열을 뒤집게 됩니다.

수열							호출 회수
2	3	5	6	7	4	1	1

수열							호출 회수
2	3	5	6	1	4	7	2

 

 이후 생각 2.에 따라 각 숫자가 자신의 자리를 찾아간다고 생각하는 겁니다.

수열							호출 회수
2	3	5	6	1	4	7	2

 생각하기 쉽게 제일 작은 수부터 앞으로 간다고 생각합니다.

 1앞에는 1보다 큰 수가 4개 있습니다.

수열							호출 회수
2	3	5	6	1	4	7	2

수열							호출 회수
2	3	5	1	6	4	7	3

수열							호출 회수
2	3	1	5	6	4	7	4

수열							호출 회수
2	1	3	5	6	4	7	5

수열							호출 회수
1	2	3	5	6	4	7	6

 2,3 앞에는 자신보다 큰 수가 없습니다. 

수열							호출 회수
1	2	3	5	6	4	7	6

수열							호출 회수
1	2	3	5	6	4	7	6

 

 4 앞에는 자신보다 큰 수가 2개 있습니다. 

수열							호출 회수
1	2	3	5	6	4	7	6

수열							호출 회수
1	2	3	5	4	6	7	7

수열							호출 회수
1	2	3	4	5	6	7	8

 5,6,7 앞에 자신보다 큰 수가 없으므로 정답은 8이 됩니다.

 생각 2.를 행하면서 생각하기 쉽게 작은 수부터 바뀌는 수를 봤으나,

 이는 그냥 모든 수가 자신보다 앞에 있는 큰 수의 개수를 더한 것과 같습니다.

 다시 한번 생각 1.이 끝난 상태를 보겠습니다.

수열							호출 회수
2	3	5	6	1	4	7	2

 

 각 수의 자신보다 앞에 있는 자신보다 큰 수를 살펴보면 다음과 같습니다.

수열								호출 회수
	2	3	5	6	1	4	7	2
자기 앞 큰 수 개수	0	0	0	0	4	2	0	+6

 이에 따라 생각 2.를 행하는 데는 6의 호출 회수가 필요하다는 걸 알 수  있습니다.

 따라서 2 + 6 = 8 이 답이 됩니다.

(1) 코드 10~23

 과정(0)의 생각 1.을 투포인터로 구현하는 함수입니다.

(2) 코드 25~40

 과정(0)의 생각 2.를 구현하기 위한 fenwick tree를 짜놓았습니다.

(3) 코드 41~50

 과정(0)의 생각 2.를 구현하는 함수입니다.

 수열을 뒤에서부터 탐색하면서 자신보다 앞에 있는 큰 수를 세주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const int MAX = 100005;
	int N;
	int arr[MAX];
	ll R; // 정답
	void Rev() { // 투 포인터
	int l = 1;
	int r = 1;
	while (l < N + 1) { // 내림차순 찾아서 뒤집기!
	r++; // r 한칸 전진
	if (r == N + 1 || arr[r - 1] < arr[r]) { // 내림차순 끝나는 지점 찾기
	if (l + 1 < r) { // 한개이면 reverse 하는 이유가 없음
	reverse(arr + l, arr + r); // l 이상 r 미만 돌리기
	++R;
	}
	l = r; // 땡겨오기
	}
	}
	}
	int fenwick[MAX];
	int Li(int x) { return x & (-x); }
	void update(int x, int diff) {
	while (x < MAX) {
	fenwick[x] += diff;
	x += Li(x);
	}
	}
	int sum(int x) { // x 이하 개수
	int ret = 0;
	while (x > 0) {
	ret += fenwick[x];
	x -= Li(x);
	}
	return ret;
	}
	void step_by_step() {// 2개씩 돌리면서 자리 맞춰갈 거임
	// 뒤에서 부터 탐색
	//i번째 수를 볼 때, 이 앞에 i번째 수보다 큰 수가 몇개 있는지 세기
	for (int i = N; i > 0; i--) {
	int curr = arr[i];
	int cnt = sum(N) - sum(curr); // 전체 - (현재 수 이하의 수) = 현재수 초과 수
	R += cnt;
	update(curr, -1); // 현재 수 지우기.
	}
	}
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> arr[i];
	Rev();
	// 처음엔 전체 수 다있다.
	for (int i = 1; i <= N; ++i) update(i, 1);
	step_by_step();
	cout << R << '\n';
	return 0;
	}

view raw BOJ 2832.cpp hosted with ❤ by GitHub