[자료구조] 백준 문제 풀이 - 1158 요세푸스 문제

난 리스트+큐로 풀었지만 큐만으로도 풀수 있는 문제

 

[내 풀이]

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


int main()
{
	list <int> circle;
	list <int>::iterator iter=circle.begin();
	queue <int> result;
	int n; cin>>n;
	int k; cin>>k;
	for(int i=1; i<=n; i++)
		circle.push_back(i);
	
	while(!circle.empty())
	{
		for(int i=0; i<k; i++) 
		{
			iter++;
			if(iter==circle.end()) // iter가 마지막 데이터 + 1 위치에 있으면
			{
				iter=circle.begin(); //처음으로 돌려보냄
			}
		}
		result.push(*iter);
		iter=circle.erase(iter);
		iter--;
	}
    //이 밑은 출력하는 코드
	cout<<"<";
	while(result.size()!=1)
	{
		cout<<result.front()<<", ";	
		result.pop();
	}
	cout<<result.front()<<">"<<endl;
}

ex) 7 3 입력하면 3 6 2 7 5 1 4 가 출력 됨

 

원형이란 말에 과몰입 해서 큐문제지만 리스트를 사용함

 

 

[다른 사람들의 풀이] - 큐를 이용함 (큐로도 원형을 구현할수 있다!)

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

int main() {
	int N, K;
	cin >> N >> K;
	queue<int> circle;
	for (int i = 0; i < N; i++)
        {
		circle.push(i + 1);
	}
	cout << "<";
	while (circle.size() - 1) //사이즈가 1개씩 줄어드는데, 큐에 데이터 1개 남을때까지
        {
		for (int i = 0; i < K - 1; i++) 
                {
			circle.push(circle.front()); //원형을 구현 !!
			circle.pop();
		}
		cout << circle.front() << ", ";
		circle.pop();
	}
	cout << circle.front() << ">";
	return 0;
}