[백준 1158] 요세푸스 문제 (cpp, queue)

🚀  들어가며...

• queue를 사용하였다.
• 입력 : 7 3 이면 -> 1 2 3 (3출력) 4 5 6 (6출력) 7 1 2 (2출력) 하는 문제이다

 

🔗  문제

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

1158번: 요세푸스 문제

 

📑  내용

처음에 큐에 모든 수를 넣고.

queue의 front를 조건 만족 시 출력해준다.

이때 선형 구조를 만족 시키기 위해서, front를 출력하지 않을 시, 다시 push 해준다.

아래가 핵심 부분이다.

// 항상 출력 대상, 검사의 대상은 queue의 front이다.
while(!q.empty()){
    for(int i=0; i<m; i++){
        // 원형 구조를 유지시키기 위해서, 다시 push
        if(i != m-1)
            q.push(q.front());
        // i == m-1일 경우 출력
        else if(q.size() == 1)
            cout << q.front();
        // q.size == 1 && i == m-1 인 경우 (마지막 출력)
        else
            cout << q.front() << ", ";

        // 원형 구조 유지가 아닌 경우 -> pop()
        // 원형 구조 유지를 위해서, front 다시 push -> front를 pop()
        q.pop();
    }
}

 

💌 소스코드

#include<iostream>
#include<queue>

using namespace std;

int main(){
	queue<int> q;
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		q.push(i);
	cout<<"<";
	while(!q.empty()){
		for(int i = 0; i < m; i++){
			if(i != m-1)
				q.push(q.front());
			else if(q.size() > 1) 
				cout<<q.front()<<", ";
			else
				cout<<q.front();
			q.pop();
		}
	}
	cout<<">";	
}