백준 23336 c++ "A Sorting Problem" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 inversion Counting 응용 문제이다.

퀵솔트나 합병 정렬로도 문제를 풀 수 있다.

필자는 세그먼트를 이용하여 문제를 해결하였고 주어지는 값들이 N보다 작거나 같기 때문에

좌표 압축은 해줄 필요 없었다.

 

[코드 해설]

코드 설명

 

세그먼트 트리 초기화

• vector<long> tree는 세그먼트 트리를 저장하기 위한 벡터로 사용됩니다.
• tree의 크기는 N * 4로 설정하여 필요한 메모리를 할당합니다. 이는 세그먼트 트리의 최대 노드 개수를 커버하기 위함입니다.

업데이트 함수 (Update)
Update 함수는 세그먼트 트리에 특정 인덱스의 값을 추가하는 역할을 합니다.

• 기저 조건: 현재 노드가 업데이트하려는 인덱스에 도달하면 값을 증가시킵니다.
• 범위 확인: 인덱스가 현재 구간에 포함되지 않으면 함수를 종료합니다.
• 재귀 호출: 현재 구간을 좌측 자식과 우측 자식으로 나누어, 적절한 자식 노드에 대해 다시 호출합니다.
• 노드 값 갱신: 자식 노드들의 합으로 부모 노드 값을 갱신합니다.

쿼리 함수 (Query)
Query 함수는 주어진 구간 [left, right]의 합을 반환합니다.

• 완전히 포함된 경우: 현재 구간이 요청한 구간에 완전히 포함되면, 현재 노드의 값을 반환합니다.
• 범위 밖인 경우: 현재 구간이 요청한 구간과 겹치지 않으면 0을 반환합니다.
• 부분적으로 포함된 경우: 좌측 자식과 우측 자식을 재귀적으로 호출하여 두 값을 더합니다.

게임 로직 (Game_Start 함수)

• 입력 처리:
  1. N (숫자 개수)을 입력받습니다.
  2. 세그먼트 트리를 N * 4 크기로 초기화합니다.
• 역순 카운팅 계산:
  1. 각 입력 값 num에 대해:
     • Query(1, 1, N, num + 1, N) 호출을 통해 현재 숫자보다 큰 숫자의 개수를 계산합니다.
     • 해당 값을 count에 누적합니다.
     • Update(1, 1, N, num, 1)을 호출하여 현재 숫자를 세그먼트 트리에 추가합니다.
  2. 위 과정을 통해 역순 카운팅의 총합을 계산합니다.
• 결과 출력: 최종적으로 count 값을 출력합니다.

메인 함수

• ios::sync_with_stdio(false)와 cin.tie(0)을 사용하여 입출력 속도를 최적화합니다.
• Game_Start를 호출하여 게임 로직을 실행합니다.

---

핵심 기능

• 세그먼트 트리 활용:
  • 입력 값의 역순 카운팅(현재 숫자보다 큰 숫자의 개수)을 효율적으로 계산합니다.
  • 각 숫자의 위치 정보를 업데이트하며, 구간 합을 통해 결과를 도출합니다.
• 시간 복잡도:
  • 각 업데이트 및 쿼리 호출의 시간 복잡도는 O(logN)입니다.
  • 전체 숫자에 대해 O(NlogN)의 시간 복잡도로 계산을 수행합니다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<long> tree;
int N;

void Update(int node, int start, int end, int idx, int diff) {
	if (start == end) {
		tree[node] += diff;
		return;
	}
	if (idx < start || end < idx)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];
}

long Query(int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		return tree[node];
	}
	if (end < left || right < start)return  0;
	int mid = (start + end) / 2;
	return Query(node * 2, start, mid, left, right) +
		Query(node * 2 + 1, mid + 1, end, left, right);
}

void Game_Start() {
	cin >> N;
	tree.resize(N * 4);

	long count = 0;
	for (int i = 0; i < N; i++) {
		long num;
		cin >> num;
		count += Query(1, 1, N, num + 1, N);
		Update(1, 1, N, num, 1);

	}
	cout << count;

}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	Game_Start();

}