백준 12899 c++ "데이터 구조" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리를 이용하여 몇번째 숫자를 찾는 응용 문제이다.

필자는 사전에 구슬문제를 통해 몇번째 숫자를 찾는게 익숙하여 해당 문제는 쉽게 해결할 수 있었다.

조심해야 될점은 입력되는 숫자의 범위가 2000000이라는 점이다.

트리의 크기를 이것보다 크게 잡아야 된다.!

[코드 해설]

 

• 세그먼트 트리 초기화 및 업데이트
  tree 벡터를 사용하여 세그먼트 트리를 관리합니다. 이 트리는 특정 구간의 값을 효율적으로 갱신하고 조회할 수 있도록 설계되었습니다.
  • Update 함수:
    • idx 위치의 값을 변경하는 함수입니다.
    • start와 end는 현재 구간을 나타내며, node는 세그먼트 트리의 현재 노드입니다.
    • 만약 start == end이면 리프 노드이므로 해당 값을 diff만큼 더하거나 뺍니다.
    • 이후 구간이 겹치는 경우, 자식 노드들(node * 2, node * 2 + 1)로 내려가 갱신을 진행하며, 부모 노드의 값은 자식 노드 값의 합으로 갱신됩니다.
• 특정 순위 조회 (Query 함수)
  Query 함수는 세그먼트 트리를 이용해 특정 순위에 해당하는 값을 빠르게 조회합니다.
  • count는 조회하려는 순위를 나타냅니다.
  • 노드의 왼쪽 자식에 순위 값이 충분히 포함되어 있으면 왼쪽으로 내려가고, 부족하면 오른쪽으로 내려가며 순위를 조정해 나갑니다.
  • 리프 노드에 도달하면 해당 순위에 해당하는 실제 값을 반환합니다.
• 게임 시작 (Game_Start 함수)
  • 입력 처리:
    • 게임 횟수 N을 입력받고, 최대 크기 3000000×43000000 \times 43000000×4를 가지는 세그먼트 트리를 초기화합니다.
  • 명령 처리:
    • 플래그 1:
      • 특정 idx에 아이템을 추가합니다. 이를 위해 Update 함수를 호출하여 세그먼트 트리에서 해당 위치의 값을 1 증가시킵니다.
    • 플래그 2:
      • 특정 순위 count에 해당하는 아이템을 조회합니다.
      • Query 함수를 호출하여 해당 순위의 값을 찾아내고, 찾은 값을 Update 함수로 감소시키며 제거합니다.
      • 조회된 값을 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<long> tree;

void Update(int node,int start,int end, int idx, int diff) {
	if (start == end) {
		tree[node] += diff;
		return;
	}

	if (idx<start || idx>end)return;

	int mid = (start + end) / 2;
	if (mid >= idx) {
		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 count) {
	if (start == end) {
		return start;
	}

	int mid = (start + end) / 2;
	if (tree[node * 2] >= count) {
		return Query(node * 2, start, mid, count);
	}
	else {
		return Query(node * 2 + 1, mid + 1, end, count - tree[node * 2]);
	}
}

void Game_Start() {
	cin >> N;
	tree.resize(3000000 * 4);
	for (int i = 0; i < N; i++) {
		int flag;
		cin >> flag;
		if (flag == 1) {
			int idx;
			cin >> idx;
			Update(1, 1, 3000000, idx, 1);
		}
		else {
			int count;
			cin >> count;
			long num = Query(1, 1, 3000000, count);
			Update(1, 1, 3000000, num, -1);
			cout << num << '\n';
		}
	}
}

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