algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEASURETIME

algospot.com :: MEASURETIME

길이 N인 수열 A[]가 주어지고, A[]를 삽입정렬했을때 정렬 과정에서 숫자들을 총 몇 번이난 옮기는지 계산하는 문제이다.

 

일단 모든 노드의 값이 0인 팬윅트리를 생성한다. A[]의 요소를 왼쪽부터 탐색해서 각 값에 해당하는 팬윅트리 노드들의 값을 1씩 증가시킨다. 또한 자신보다 큰 값이 나왔던 횟수를 구하기 위해 전체 횟수 합에서 자신이하의 값이 나온 횟수합을 뺀다.

 

	#include<iostream>
	#include<vector>
	using namespace std;
	// 팬윅트리의 구현
	// 초기화시 A[]의 원소가 전부 0이라 생각
	struct FenwickTree {
	vector<int> tree;
	FenwickTree(int n) : tree(n + 1) {}
	// A[0,pos]의 부분 합을 계산
	int sum(int pos) {
	int ret = 0;
	pos++;
	while (pos > 0) {
	ret += tree[pos];
	pos &= (pos - 1);
	}
	return ret;
	}
	// A[pos]에 val을 더함
	void add(int pos, int val) {
	pos++;
	while (pos < tree.size()) {
	tree[pos] += val;
	pos += (pos & -pos);
	}
	}
	};
	// 팬윅트리를 이용해 문제를 해결
	long long countMoves(const vector<int>& A) {
	FenwickTree tree(1000000);
	long long ret = 0;
	// 배열의 요소를 하나씩 추가하면서 자기보다 큰 요소의 갯수를 구함
	for (int i = 0; i < A.size(); i++) {
	ret += tree.sum(999999) - tree.sum(A[i]);
	tree.add(A[i], 1);
	}
	return ret;
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	int n;
	cin >> n;
	vector<int> arr;
	int element;
	for (int i = 0; i < n; i++) {
	cin >> element;
	arr.push_back(element);
	}
	cout << countMoves(arr) << endl;
	}
	}

view raw algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MEASURETIME.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2