[P5] 백준 15517번 Array Manipulation at Moloco (Hard) C++ 정렬, 값/좌표 압축, 세그먼트 트리

리뷰

 

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

배열에서 현재 자신의 위치 앞쪽에 작은 수의 개수를 출력하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• arr : 배열 정보를 저장할 배열
• n : 배열의 크기를 저장할 변수

 

함수

1. update

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

 

세그먼트 트리 정보를 업데이트 하기 위한 함수

 

2. query

int query(vector<int>& tree, int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return query(tree, node * 2, s, mid, L, R) + query(tree, node * 2 + 1, mid + 1, e, L, R);
}

 

세그먼트 트리 구간합을 출력하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, 정수형 벡터 vals를 초기화한다.
2. n개의 원소를 입력 받아 arr배열을 초기화 하고, vals에 각 값을 push해준다.
3. sort함수를 통해 vals벡터를 오름차순으로 정렬한다.
4. erase, unique함수를 통해 vals에서 중복값을 제거해준다.
5. 변수 m을 vals의 크기로 저장한다.
6. 정수형 벡터 tree를 (m+1)*4크기의 기본값 0으로 초기화한다.
7. arr을 순회하며 현재 값을 변수 cur에 저장한다.
8. 변수 idx에 cur이 vals의 몇번째 인덱스에 저장되어있는지를 저장한다.
9. query함수를 통해 세그먼트 트리의 1~idx인덱스의 구간합을 구해 출력 후 개행문자를 삽입해 줄바꿈을 수행한다.
10. update함수를 통해 세그먼트 트리의 idx+1인덱스 값을 1만큼 증가시킨다.
11. 위 로직을 arr을 모두 순회할때까지 수행해준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 중복값이 들어오지 않는다는 이야기가 없었으므로 중복값을 제거해주었다.
2. 또한 중복 제거 후의 vals크기를 기준으로 세그먼트 트리를 초기화해주었다.
3. 1-based-indexing을 위해 lower_bound로 구한 idx에 1을 더해주었다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 1e6;
int arr[N];
int n;

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

int query(vector<int>& tree, int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return query(tree, node * 2, s, mid, L, R) + query(tree, node * 2 + 1, mid + 1, e, L, R);
}

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

	cin >> n;
	vector<int> vals;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
		vals.push_back(arr[i]);
	}

	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());

	int m = vals.size();
	vector<int> tree((m + 1) * 4, 0);

	for (int i = 0; i < n; ++i) {
		int cur = arr[i];
		int idx = lower_bound(vals.begin(), vals.end(), cur) - vals.begin();

		cout << query(tree, 1, 1, m, 1, idx) << "\n";
		update(tree, 1, 1, m, idx + 1);
	}
}