[P4] 백준 12899번 데이터 구조 C++ 세그먼트 트리

리뷰

 

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

세그먼트 트리를 활용한 배열에 값을 삽입/삭제하고, k번째 작은 수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 저장할 정수형 상수 변수
• n : 쿼리의 개수를 저장할 정수형 변수
• t : 쿼리의 종류를 입력 받기 위한 변수
• x : 쿼리의 값을 입력 받기 위한 변수
• tree : 세그먼트 트리 정보를 저장할 정수형 배열

 

함수

1. update

void update(int node, int s, int e, int idx, int val)

 

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

1. 매개변수로 현재 세그먼트 트리의 노드 node, 탐색 범위 s, e, 변경할 값의 인덱스 idx, 삽입/제거 여부 val을 전달받는다.
2. 리프 노드에 도달했을 경우 현재 노드에 val값을 증가시켜 준다.
3. 리프 노드가 아니라면 탐색 범위의 mid값을 구해준다.
4. idx가 mid보다 작거나 같다면 왼쪽으로, 크다면 오른쪽 노드로 재귀를 진행한다.
5. 재귀를 빠져나오며 현재 노드의 값을 좌우 자식 노드의 값의 합으로 갱신해 준다.

 

2. query

int query(int node, int s, int e, int k)

 

쿼리를 통해 k번째 작은 수를 출력하기 위한 함수

1. 매개변수로 현재 세그먼트 트리의 노드 node, 탐색 범위 s, e, 현재 탐색 중인 k번째 작은 값을 전달받는다.
2. 리프 노드에 도달했을 경우 s나 e중 아무거나 리턴해 준다.
3. 리프 노드가 아니라면 탐색 범위의 mid값을 구해준다.
4. 좌측 자식 노드의 값이 k보다 크거나 같은 경우 왼쪽으로 재귀를 진행해 준다.
5. k보다 작다면 오른쪽으로 재귀를 진행한다, 이 때 k값은 k - 좌측 자식 노드의 값으로 전달해 준다.

 

문제풀이

1. n값을 입력 받은 후 n번의 while루프를 수행하고, 매 루프마다 t, x에 값을 입력받는다.
2. t가 1이라면 update 함수를 통해 x번째 인덱스에 1만큼 더해준다.
3. 아니라면 정수형 query함수를 통해 변수 result에 x번째 작은 수를 저장해 준다.
4. result에 저장된 값을 출력해 주고, result번째 인덱스에 -1만큼 더해준다.

 

트러블 슈팅

1. query출력 후 update 시 인덱스를 쿼리의 반환값이 아닌 x로 했다가 Fail을 받았다.
2. query의 반환값을 result에 저장하고, result출력 후 result를 기준으로 update를 했더니 AC를 받았다.

 

참고 사항

• X값으 범위가 1 ~ 200만이므로 해당 값들을 세그먼트 트리의 인덱스로 활용하면 된다.
• 각 노드의 값은 노드가 속한 구간에 요소가 몇개나 있는지를 저장한다.
• 따라서 만약 5번째 작은 수를 구하고 싶은데 좌측 자식 노드의 값이 4라면 우측 자식 노드에서 1번째로 작은 수를 구해주면 된다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 2000001;
int n, t, x;
int tree[N * 4];

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

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

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

	cin >> n;
	while (n--) {
		cin >> t >> x;
		if (t == 1) update(1, 1, N - 1, x, 1);
		else {
			int result = query(1, 1, N - 1, x);
			cout << result << "\n";
			update(1, 1, N - 1, result, -1);
		}
	}
}