[C++] BOJ 1157번 - 요세푸스 문제

📖 Problem

---

🔓 Solve

---

가장 먼저 든 생각은, 큐에서 제거할 사람의 위치를 특정하고, 그만큼 pop을 수행하여 그 위치로 이동하고, 대상을 제거한 후에, pop을 한만큼 다시 push를 해주는 것이었다.

이 때 대상의 위치는 K % (큐의 size) 로 구할 수 있다.

그런데 문제에서 요구하는 것은 대상을 제거하고, 해당 위치에서 탐색을 재개하는 것이다.

따라서 큐에서 대상까지 가면서 pop과 동시에 push를 진행하였다. 이러면 자연스럽게 데이터들은 뒤로 순서가 밀리게 된다.

이를 큐가 빌 때까지 반복문으로 반복해주면 된다.

💻 Code

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	// input

	queue<int> que;
	vector<int> result;
	result.reserve(5000);
	// store result

	for (int count = 1; count <= N; count++) {
		// queue initialize
		que.push(count);
	}

	while (!que.empty()) {
		int pos = K % que.size();
		// if pos == 1, it indicates first data
		// if pos == 0, it indicates last data

		int count;
		if (pos == 0) {
			// exception case : last data
			count = que.size() - 1;
		}
		else {
			count = pos - 1;
		}
		
		for (int i = 0; i < count; i++) {
			// readjust position of data
			que.push(que.front());
			que.pop();
		}
		result.push_back(que.front());
		que.pop();
		
	}

	// print
	cout << "<";
	for (int index = 0; index < result.size() - 1; index++) {
		cout << result[index] << ", ";
	}
	cout << result[result.size() - 1] << ">" << endl;
}

큐에서 데이터를 pop하면서 동시에 push를 할 생각만 하면 구현은 어렵지 않은 문제이다.

---

---

⚡개인적으로 공부하면서 포스팅한 글입니다. 오류가 있는 경우 지적해주시면 감사하겠습니다!⚡