문제

출처 : https://www.algospot.com/judge/problem/read/MEASURETIME

유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽입 정렬의 구현은 다음과 같습니다.

void insertionSort(vector<int>& A) {
  for(int i = 0; i < A.size(); ++i) {
    // A[0..i-1] 에 A[i] 를 끼워넣는다
    int j = i;
    while(j > 0 && A[j-1] > A[j]) {
      // 불변식 a: A[j+1..i] 의 모든 원소는 A[j] 보다 크다.
      // 불변식 b: A[0..i] 구간은 A[j] 를 제외하면 정렬되어 있다.
      swap(A[j-1], A[j]);
      --j;
    }
  }
}

삽입 정렬은 A[0..i-1] 이 정렬된 배열일 때, A[i] 를 적절한 위치를 만날 때까지 왼쪽으로 한칸씩 움직입니다. 예를 들어 A={5,1,4,3,2} 의 삽입 정렬은 다음과 같이 이루어집니다.

길이 N 인 수열 A[] 가 주어집니다. 이 정렬 과정에서 숫자들을 총 몇 번이나 옮기는지를 계산하는 프로그램을 작성하세요. 예를 들어 위 배열의 경우 총 1+1+2+3=7 번 숫자를 옮기게 됩니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 원 배열의 길이 N (1 <= N <= 50000) 이 주어집니다. 그 다음 줄에 N개의 정수로 A의 원소 Ai가 주어집니다. (0 <= Ai < 1,000,000)

입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

출력

각 테스트 케이스마다 한 줄에 A를 삽입정렬하는 과정에서 숫자를 옮기는 총 횟수를 출력합니다.

풀이

이 문제는 펜윅 트리를 활용하여 푸는 문제인데, 펜윅트리는 빠르고 간단하게 구간합을 계산하기 위한 트리 구조이다. 구현은 다음과 같다.

class FenwickTree{
	int tree[];
	
	FenwickTree(int n){
		tree = new int[n+1];
	}
	
	int sum(int pos) {
		// 비트연산을 위해 인덱스를 1부터 생각
		++pos;
		int ret = 0;
		while(pos > 0) {
			ret += tree[pos];
			pos &= (pos-1);
		}
		return ret;
	}
	
	void add(int pos, int val) {
		++pos;
		while(pos <tree.length) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}	
	
}

1차원 배열 tree에 각 요소값이 저장되며, sum과 add메소드에 비트연산을 통해 적절한 배열 범위에 접근할 수 잇다. 이 때, 시작 인덱스를 비트연산을 수행하기 위해 1로 설정하기 위해 인덱스에 1을 더하여 연산한다. 합치는 연산 sum의 경우 pos & pos-1 을 통해 이진수의 마지막 비트를 지운 구간을 계산하여 부분합의 다음 요소에 접근하고, 더하는 연산 add의 경우 pos & -pos를 통해 맨 오른쪽이 1인 비트를 스스로에게 더한 값을 계산하여 자신을 포함하는 다음 요소에 접근한다. 이렇게 구현한 펜윅 트리를 통해 부분합을 빠르게 계산할 수 있다.

문제의 경우, 배열에서 삽입정렬이 수행될 때 A[0…i-1] 구간까지 A[i]보다 큰 값이 몇 개 있는지 파악해야 한다. 따라서, 앞서 구현한 펜윅트리에 각 숫자의 등장 횟수를 순차적으로 저장하도록 한다. 배열의 첫 요소부터 시작하여 모든 숫자의 등장 횟수 중 A[i]까지의 등장 횟수의 부분합을 빼서 A[i]보다 큰 값들의 등장 횟수를 계산하고, 각 요소값에 등장 횟수를 1씩 더한다.

static double countMoves(int[] A) {
		FenwickTree tree = new FenwickTree(1000000);
		double ret = 0;
		for(int i=0;i<A.length;i++) {
			ret+= tree.sum(999999)-tree.sum(A[i]);
			tree.add(A[i], 1);
		}
		return ret;
	}

문제에서 주어진 입력값의 범위가 100만까지이므로 999999까지의 합은 전체 숫자의 등장 횟수고, A[i]까지의 부분합은 A[i] 까지의 등장 횟수의 부분합이므로 두 값을 빼면 삽입 정렬이 일어나는 조건인 더 큰 값의 개수를 구할 수 있다.