[P4] 백준 1849번 순열 C++ 세그먼트 트리

리뷰

 

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

구간 합 세그먼트 트리를 통해 답을 도출하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 저장할 상수 변수
• n : 수열 원소의 개수를 저장할 변수
• s : 매 원소를 입력 받을 변수
• lst : 초기엔 모두 1로, 이후엔 수열의 순서로 저장할 배열
• tree : 세그먼트 트리 정보를 저장할 배열

 

함수

1. build

void build(int node, int s, int e) {
	if (s == e) tree[node] = lst[s];
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

 

세그먼트 트리 초기화를 진행할 함수

 

2. update

void update(int node, int s, int e, int idx) {
	if (s == e) --tree[node];
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

 

세그먼트 트리 업데이트를 진행할 함수

 

3. query

int query(int node, int s, int e, int val) {
	if (s == e) return s;
	int mid = (s + e) / 2;
	if (val < tree[node * 2]) return query(node * 2, s, mid, val);
	return query(node * 2 + 1, mid + 1, e, val - tree[node * 2]);
}

 

구간합을 사용해 현재 원소의 수열 내 인덱스를 구하는 함수

 

 

문제풀이

• n값을 입력 받고, lst배열의 1~n값을 모두 1로 저장해 준다.
• build함수를 통해 세그먼트 트리 초기화를 진행해 준다.
• 1~n을 순회하며 매 루프마다 s에 값을 입력 받아준다.
• query함수에 s를 전달하여 변수 idx에 현재 원소가 삽입될 인덱스를 구해준다.
• lst의 idx에 i를 저장해 주고, update함수에 idx를 전달하여 세그먼트 트리의 해당 노드의 값을 0으로 만들어 준다.
• 쿼리를 모두 수행한 후 lst배열의 1~n인덱스에 저장된 값을 줄 바꿈을 기준으로 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 초기값을 모두 1로 설정하고, 세그먼트 트리 누적합이 s인 노드의 인덱스를 뽑아내면 원소가 들어가야 할 인덱스다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5 + 1;
int n, s;
int lst[N];
int tree[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = lst[s];
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

void update(int node, int s, int e, int idx) {
	if (s == e) --tree[node];
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int query(int node, int s, int e, int val) {
	if (s == e) return s;
	int mid = (s + e) / 2;
	if (val < tree[node * 2]) return query(node * 2, s, mid, val);
	return query(node * 2 + 1, mid + 1, e, val - tree[node * 2]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) lst[i] = 1;
	build(1, 1, n);

	for (int i = 1; i <= n; ++i) {
		cin >> s;
		int idx = query(1, 1, n, s);
		//cout << "result of query : " << idx << "\n";
		lst[idx] = i;
		update(1, 1, n, idx);
	}

	for (int i = 1; i <= n; ++i) cout << lst[i] << "\n";
}