[P5] 백준 1777번 순열복원 C++ 세그먼트 트리

리뷰

 

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

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

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

위 문제의 반대 버전

 

 

전역 변수

• N : 순열의 최대 크기를 저장할 상수 변수
• n : 순열의 크기를 저장할 변수
• s : 각 인버전 시퀀스 값을 저장할 변수
• lst : 순열의 인버전 시퀀스를 저장할 배열
• ans : 순열의 요소를 저장할 배열
• 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 + 1]) return query(node * 2 + 1, mid + 1, e, val);
	return query(node * 2, s, mid, val - tree[node * 2 + 1]);
}

 

인버전 시퀀스 값을 기준으로 순열의 몇번째 요소에 값이 할당되어야 하는지를 구하기 위한 함수

 

 

문제풀이

• n값을 입력 받고, lst배열의 1~n번째 인덱스를 모두 1로 초기화 해준다.
• build함수를 통해 누적합 세그먼트 트리를 초기화 해준다.
• lst배열의 1~n번째 인덱스에 인버전 시퀀스 값을 입력 받아준다.
• n부터 1번인덱스 까지 역순으로 순회하며 lst배열의 현재 인덱스 값을 변수 s에 저장해 준다.
• 변수 idx에 쿼리 함수에 s를 매개변수로 전달하여 리턴받은 값을 저장해 준다.
• ans의 idx에 i를 저장해 주고, update함수에 idx를 전달하여 세그먼트 트리 업데이트를 진행해 준다.
• 모든 쿼리가 수행된 후 ans의 배열의 1~n까지 저장된 값을 공백을 기준으로 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 규칙성이 시퀀스를 뒤에서부터 탐색할때 발생한다는 것을 깨달으면 순열문제와 유사하다는 것을 알 수 있다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5 + 1;
int n, s;
int lst[N];
int ans[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 + 1]) return query(node * 2 + 1, mid + 1, e, val);
	return query(node * 2, s, mid, val - tree[node * 2 + 1]);
}

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 >> lst[i];
	for (int i = n; i >= 1; --i) {
		s = lst[i];
		int idx = query(1, 1, n, s);
		//cout << "result of query : " << idx << "\n";
		ans[idx] = i;
		update(1, 1, n, idx);
	}

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