[P3] 백준 1168번 요세푸스 문제 2 C++ 세그먼트 트리

리뷰

 

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

배열을 순회하며 k번째 사람을 제거하고 출력하는 문제

이전에 풀었던 데이터 구조 문제와 유사하나 살짝 더 응용한 문제였다.

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

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

 

 

전역 변수

1. N : 배열의 최대값을 저장하기 위한 정수형 상수 변수
2. n : 사람의 수를 저장하기 위한 변수
3. k : 사람을 순회할 때 건너 뛰기 위한 인덱스
4. tree : 세그먼트 트리 정보를 저장할 정수형 배열

 

함수

1. build

void build(int node, int s, int e)

 

세그먼트 트리 정보를 초기화 하기 위한 함수

1. 매개변수로 노드의 번호 node, 탐색 범위 s, e를 전달 받는다.
2. 기저 조건으로 리프 노트에 도달했을 경우 해당 노드의 값을 1로 저장해 준다.
3. 리프 노드가 아닐 경우 좌, 우 자식 노드로 재귀를 진행한다.
4. 재귀를 빠져나오면 현재 노드의 값을 좌, 우 자식 노드의 값의 합으로 저장해 준다.

 

2. query

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

 

세그먼트 트리를 순회하며 k번째 인덱스를 출력하기 위한 함수

1. 기저 조건으로 리프 노드에 도달하면 해당 노드의 값을 0으로 변경하고 s를 리턴한다.
2. 리프 노드가 아닐경우 정수형 변수 result를 초기화 해준다.
3. k가 왼쪽 자식 노드보다 작거나 같을 경우 왼쪽 노드로 재귀를 진행하고 리턴값을 result에 저장한다.
4. 클 경우 오른쪽 노드로 재귀를 진행하고 리턴값을 result에 저장한다.
5. 재귀를 빠져나온 후 트리 정보를 업데이트 해준 후 result값을 리턴해 준다.

 

문제풀이

1. n, k값을 입력 받아준 후 build함수를 통해 세그먼트 트리의 초기화를 진행해 준다.
2. 정수형 벡터 ans를 초기화 하고, 정수형 변수 idx에 k값을 저장해 준다.
3. n번의 반복문을 기행해 주고, query함수를 통해 idx번째 요소를 찾아 ans에 push해준다.
4. 만약 i가 n - 1보다 작다면 idx에 k - 1만큼 더해준 후 tree의 루트 노드에 저장된 값으로 나눈 나머지를 저장한다.
5. 저장된 idx의 값이 0이라면 tree의 루트 노드에 저장된 값으로 변경해 준다.
6. "<"를 출력하여 순열의 시작임을 명시해 주고, 다시 n번의 반복문을 수행해 준다.
7. ans의 i번째 저장된 값을 출력해 주고, i가 n - 1보다 작다면 ", "를 추가로 출력해 준다.
8. 모든 순회를 마친 후 ">"를 출력하여 순열의 마지막임을 명시해 준다.

 

트러블 슈팅

1. idx가 0일 경우 트리의 첫번째 노드를 탐색하게 되어 올바른 답을 찾지 못했다.
2. idx가 0일 경우 idx의 값을 트리의 루트 노드에 저장된 값으로 변경해 주니 예제가 잘 나왔고 제출 시 AC를 받았다.

 

참고 사항

• query실행 후 루트 노드의 값이 1만큼 줄었기 때문에 idx + k가 아닌 idx + k - 1을 해주어야한다.
• 쿼리문 내부에서 리프 노드 도달 및 재귀를 빠져나오며 update까지 진행해 주었다.

 

정답 코드

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

const int N = 100001;
int n, k;
int tree[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = 1;
	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];
	}
}

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

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

	cin >> n >> k;
	build(1, 1, n);

	vector<int> ans;
	int idx = k;
	for (int i = 0; i < n; ++i) {
		int result = query(1, 1, n, idx);
		ans.push_back(result);
		if (i < n - 1) {
			idx = (idx - 1 + k) % tree[1];
			if (idx == 0) idx = tree[1];
		}
	}

	cout << "<";
	for (int i = 0; i < n; ++i) {
		cout << ans[i];
		if (i < n - 1) cout << ", ";
	}
	cout << ">";
}