백준 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.를 구현하는 함수입니다.

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