[백준 알고리즘 c++] 문제 26.요세푸스 문제 0 11866

문제
요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력
예제와 같이 요세푸스 순열을 출력한다.

내 풀이 queue 사용)

#include <iostream>
#include <queue>

using namespace std;

int main()
{

	//
	// 문제
	// 1. N 명의 사람들 에서 K번째 사람을 제거하는 규칙을 만들어라
	// 입력
	// 1. N명과 K번째를 입력받는다.
	// 처리
	// 1. while문을 돌려 큐의 사이즈가 1이 될때 까지 반복한다.
	// 2. 큐에서 3번째 것을 제외한 나머지만 push 되게하는 큐를 하나 더 만든다.
	// 2-1. 리사이즈 큐에서 count 만큼을 나눈 나머지값부분의 원소를 제외한 원소를 큐에 저장한다.
	// 3. 3번째 것은 출력한다
	// 4. 사이즈가 1이 될때 까지 반복한다.
	// 출력

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N = 0;
	int K = 0;
	cin >> N >> K;

	queue<int> que;
	for (int i = 1; i <= N; i++)
	{
		que.push(i);
	}

	int count = K;
	int maxSize = que.size();

	cout << "<";

	while (1)
	{
		if (que.size() == 1)
		{
			cout << que.front() << ">";
			break;
		}

		queue<int> que2;
		queue<int> que3;
		que3 = que;



		for (int i = 1; i <= que.size(); i++)
		{
			int num = que3.front();
			que3.pop();

			//int t = count % que.size();

			if (count == 0)
			{
				count = que.size();
			}


			if (i != count)
			{
				que2.push(num);
			}
			else
			{
				cout << num << ", ";
			}
		}

		//		//이전 위치 + 카운트
		//count = count + K - 1;
		//
		//if (count == K)
		//{
		//	count = K;
		//}

		//if (count > maxSize)
		//{
		//	count = count - maxSize;
		//}

		count = (count + K - 1) % que2.size();


		//que를 재구성해준다.
		swap(que, que2);

	}


	return 0;
}

내 풀이 deque 사용)

#include <iostream>
#include <deque>

using namespace std;

int main()
{

	//
	// 문제
	// 1. N 명의 사람들 에서 K번째 사람을 제거하는 규칙을 만들어라
	// 입력
	// 1. N명과 K번째를 입력받는다.
	// 처리
	// 1. while문을 돌려 큐의 사이즈가 1이 될때 까지 반복한다.
	// 2. K 번째 만큼 이동하기 위해 K 를 
	// 출력
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	deque<int> dq;
	
	int K = 0;
	int N = 0;

	cin >> N >> K;
	
	//1,2,3,4,5
	for (int i = 1; i <= N; i++)
	{
		dq.push_back(i);
	}

	deque<int>::iterator iter = dq.begin();

	int count = 1;

	cout << "<";
	
	while (1)
	{

		if (dq.size() == 1)
		{
			cout << *iter << ">";
			break;
		}


		if (count % K == 0)
		{
			cout << *iter << ", ";
			iter = dq.erase(iter);
			count = 1;
		}
		
		if (iter == dq.end())
		{
			iter = dq.begin();
		}

		if (K != 1)
		{
			iter++;
		}
		count++;


		if (iter == dq.end())
		{
			iter = dq.begin();
		}
			
	}
	
	
	

	return 0;
}

좀더 간략하게 문제를 풀수 있다.

다른풀이 queue )

#include <iostream>
#include <queue>
using namespace std;
 
int main(int argc, char *argv[]) 
{
	int N, K;
	queue<int> q;
	cin >> N >> K;
 
	for (int i = 1; N >= i; i++) {
		q.push(i);
	}
	
	cout << "<";
	while (!q.empty()) {
		for (int i = 0; i < K - 1; i++) {
			q.push(q.front());
			q.pop();
		}
 
		cout << q.front();
		q.pop();
 
		if (!q.empty()) {
			cout << ", ";
		}
 
	}
	cout << ">" << endl;
 
	return 0;
}

다른 풀이 deque)

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

vector <int> vec;
deque <int> q;

int main ()
{
	int N,M;

	//scanf("%d %d", &N, &M);
    cin >> N >> M;
	int point=0;
	int cnt=0;
	int tot_cnt=0;

	for(int i=0 ;i<N;i++)
	{
		vec.push_back(i+1);
	}
	point = M-1;
	
	if(N>1)
		printf("<%d, ",vec[point]);
	else
	{
		printf("<%d>",vec[point]);
		return 0;
	}
	// 프린트 한거는 바로 삭제시켜준다.
	vec.erase(vec.begin() + point);

	tot_cnt++;
	cnt = 1;
	
	
	while(!vec.empty())
	{
		if(point >= int(vec.size()))
			{
				point = 0;
			}
		// 포인트를 한칸씩 이동시키면서 갈 수 있는지 
		// 만약 갈 수 있다면 cnt를 ++한다.
		// 갈 수 없으면 원형 큐 처럼 포인트를 0으로 이동시킨다.
		while(cnt < M)
		{
			if(point+1 >= int(vec.size()))
			{
				point = 0;
				cnt++;
			}
			else
			{
				point++;
				cnt++;
			}
		}
		
		if(cnt == M)
		{
			if(tot_cnt <N-1)
				printf("%d, ",vec[point]);
			else
				printf("%d>",vec[point]);

			vec.erase(vec.begin() + point);
			cnt = 1;
			tot_cnt++;
		}
	}
	return 0;
}