[백준] 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

벡터에 일단 1~N을 저장해놓고 직접 지워가며 시뮬레이션하며 풀었다. 이 과정을 벡터가 빌 때까지 반복해주었다.

원형 연결리스트처럼 동작하게 하기 위해 modulo 연산을 사용해주었다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		v[i] = i + 1;
	}
	vector<int> result;
	int start = 0;
	while (!v.empty()) {
		int index = (start + k - 1) % v.size();
		result.push_back(v[index]);
		v.erase(v.begin() + index);
		if(!v.empty())
			start = index % v.size();
	}
	cout << "<";
	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
		if (i == result.size() - 1) {
			cout << ">";
		}
		else {
			cout << ", ";
		}
	}
	return 0;
}

start 변수는 K번째를 세기 시작하는 곳이다. start부터 K번째 위치를 지우면 된다.

그런데 지우고 나서가 문제이다. start로부터 K번째 위치가 index라고 하면 지우고 나서 이 위치가 start가 되면 안 된다.

예를 들어 벡터의 크기가 8이었다고 하자. 그리고 start가 5, K가 3이어서 지워야 할 위치인 index가 7이었다고 하자. 그래서 인덱스가 7인 원소를 삭제했다고 하자. 그러면 벡터의 크기는 8에서 7로 줄어드는데 그러면 인덱스 7은 벡터의 범위를 벗어났으므로 index out of range 에러가 날 것이다. 따라서 현재 vector 크기로 한 번 더 modulo 연산을 해줘야 한다.