C++ / 백준 / 1158 / 요세푸스 문제

문제

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

1158번: 요세푸스 문제

문제풀이

큐 두 개를 선언한다. 하나는 요세푸스 큐, 다른 하나는 답을 내는 용인 answer 큐를 만든다.

먼저 큐에 모든 사람을 집어넣는다.

while문을 이용해서 answer에 모든 사람을 집어넣을 때까지 반복을 한다.

현재 사람이 몇 번째인지 세기 위한 count변수를 하나 선언하고, 1부터 시작하여 K가 될 때까지 증가시킨다.

증가시키면서 요세푸스 큐의 첫 번째 값을 다시 요세푸스 큐에 push 하고 pop을 한다.

그렇게 되면 첫 번째 값을 꺼내 다시 큐 끝에 붙여 넣는 행동을 한셈이다.

만약 count변수가 K라면 요세푸스 큐의 front값을 answer에 push 하고 요세푸스 큐에서 제거한다.

이 작동을 answer에 모든 사람이 담길 때까지 반복한다.

while문이 종료되었으면 answer의 front를 출력하고 pop 하여 큐의 모든 원소를 출력하면 된다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), K(0);
	queue<int>josephus;
	cin >> N >> K;
	int idx(0);
	for (idx = 1; idx <= N; ++idx)
		josephus.push(idx);
	queue<int>answer;

	idx = 1;
	while (answer.size() < N) {
		if (idx < K) {
			josephus.push(josephus.front());
			josephus.pop();
			++idx;
		}
		else if (idx == K) {
			answer.push(josephus.front());
			josephus.pop();
			idx = 1;
		}
	}
	cout << '<';
	while (!answer.empty()) {
		cout << answer.front();
		answer.pop();
		if (!answer.empty()) cout << ", ";
	}
	cout << '>';
}

 

 

#2

number는 1부터 N까지의 값을 갖고 있는 벡터로 둔다.

-1부터 시작하여 인덱스에 K값을 더해주고 해당 번째 값을 answer 벡터에 push 하고, number에서는 erase 하여 값을 지워준다. erase 하여 값을 지웠으니 크기도 줄어들으므로 idx--을 한다.

idx+K값이 number벡터의 크기 이상이라면 idx+K값을 벡터의 크기로 나눈 나머지로 바꾼다.

이 작업을 number가 빌 때까지 반복하면 된다.

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), K(0);
	int idx(0);

	cin >> N >> K;

	vector<int>number(N, 0);
	vector<int>answer;

	for (idx = 0; idx < N; ++idx)
		number[idx] = idx + 1;
	idx = -1;

	while (!number.empty()) {
		idx += K;
		if (idx >= number.size()) {
			idx %= number.size();
		}
		answer.push_back(number[idx]);
		number.erase(number.begin() + idx);
		idx--;
	}

	cout << '<';
	for (idx = 0; idx < N; ++idx) {
		cout << answer[idx];
		if (idx < N - 1) cout << ", ";
	}
	cout << '>';
}