백준 1158번 조세퍼스 문제 (C++)

문제 링크는 다음과 같다.

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

1158번: 조세퍼스 문제

 

처음에는 직관적으로 링크드리스트를 사용해야겠다고 생각했다.

 

이후에 iterator가 리스트의 마지막을 가리키는 경우를 제대로 핸들하지 못해서

 

벡터를 이용한 풀이를 최종 풀이로 결정했었다.

 

큐를 활용하는 문제라는 것을 확인한 이후에 큐를 이용한 풀이를 작성했다.

 

큐를 휘어서 생각하면 원형의 형태로 볼 수 있다.

 

이에 착안해서 front 부분에 있는, 건너 뛰어야 할 요소들을 push 해준 이후에 pop 해주는 방식으로

 

원하는만큼 '점프'할 수 있다.

 

#include<iostream>
#include<queue>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	queue<int> q;
	int n, k;
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		q.push(i);

	cout << '<';
	while (n--) {

		for (int i = 0; i < k - 1; i++) { //pop할 때, 한번의 건너뛰는 효과를 볼 수 있다. 그래서 k-1번만 건너뛴다.
			q.push(q.front()); //front에 있는 것을 다시 push 해주고
			q.pop(); //삭제해주면 위로 올리는 효과
		}
		cout << q.front();
		q.pop();
		if (!q.empty())
			cout << ", ";
	}
	cout << '>';

	return 0;
}