백준 10090 c++ "Counting Inversion" -PlusUltraCode-

https://www.acmicpc.net/problem/10090

 

 

[필자 사고]

이 묹제는 대표적인 역순쌍 구하는 문제이다. 버블 소트의 스왑 갯수를 구하는 것과 같다.

필자는 역숙쌍의 갯수를 구하기위해 세그먼트 트리 자료구조를 이용했고

for(int i = N ;i >=1; i--) 등의 형식으로 뒤에서부터 조사를 했따.

해당 값보다 작은 값의 갯수를 구하면 된다.

[코드 해설]

 

• Input 함수
  • 이 함수는 입력값을 읽어들이는 역할을 한다.
  • 세그먼트 트리를 관리하기 위한 tree 벡터를 4×N+14 \times N + 14×N+1 크기로 초기화한다.
  • 입력된 숫자를 해당 인덱스(1부터 시작)와 매핑하기 위해 map(myMap)을 생성한다.
• Query 함수
  • 이 함수는 세그먼트 트리에서 특정 구간의 합을 구하는 역할을 한다.
  • 구간 [left,right][left, right][left,right]이 현재 노드가 담당하는 범위 [start,end][start, end][start,end]와 완전히 겹치는 경우, 해당 노드의 값을 반환한다.
  • 구간이 겹치지 않는 경우에는 0을 반환한다.
  • 부분적으로 겹치는 경우, 구간을 두 부분으로 나누어 재귀적으로 호출하여 결과를 합산한다.
• Update 함수
  • 이 함수는 세그먼트 트리의 특정 인덱스 값을 갱신하는 역할을 한다.
  • start == end일 때, 해당 노드 값을 갱신(diff를 더함)한다.
  • 그렇지 않을 경우, 트리를 두 부분으로 나누어 재귀적으로 호출하여 값을 갱신한다.
  • 호출이 끝난 뒤, 현재 노드의 값을 왼쪽 자식 노드와 오른쪽 자식 노드의 합으로 갱신한다.
• Game_Start 함수
  • 이 함수는 게임의 주요 로직을 수행한다.
  • NNN부터 1까지의 숫자에 대해 다음을 수행한다:
    • 해당 숫자의 인덱스(myMap[i])를 조회한다.
    • Query를 사용해 해당 인덱스보다 작은 값들 중 자신보다 앞에 있는 숫자들의 개수를 합산한다.
    • Update를 사용해 현재 인덱스에 해당하는 값을 세그먼트 트리에 갱신한다.
  • 결과적으로, resultCount는 앞에 위치한 자신보다 작은 숫자들의 총합을 저장하며, 이를 출력한다.
• main 함수
  • 입력과 출력을 빠르게 하기 위해 ios::sync_with_stdio(false)와 cin.tie(0), cout.tie(0)을 설정한다.
  • Input 함수를 호출해 데이터를 초기화한 뒤, Game_Start 함수로 게임을 시작한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int N;
vector<long> tree;
map<long, long> myMap;

void Input() {
	cin >> N;

	tree.resize(4 * N + 1);
	for (int i = 0; i < N; i++) {
		long num;
		cin >> num;
		myMap[num] = i+1;
	}
}

long Query(int Node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		return tree[Node];
	}
	else if (end < left || right < start) {
		return 0;
	}

	else {
		int mid = (start + end) / 2;
		return Query(Node * 2, start, mid, left, right) +
			Query(Node * 2 + 1, mid + 1, end, left, right);
	}
}

void Update(int Node, int start, int end, int idx, long diff) {
	if (start == end) {
		tree[Node] += diff;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) {
		Update(Node * 2, start, mid, idx, diff);
	}
	else {
		Update(Node * 2 + 1, mid + 1, end, idx, diff);
	}

	tree[Node] = tree[Node * 2] + tree[Node * 2 + 1];
}

void Game_Start() {

	long resultCount = 0;

	for (int i = N; i >= 1; i--) { 
		int idx = myMap[i];
		resultCount += Query(1, 1, N, 1, idx - 1); 
		Update(1, 1, N, idx, 1);
	}

	cout << resultCount;
}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}