BOJ - 1158. 요세푸스 문제

www.acmicpc.net/problem/1158

문제

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

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 ≤ 5,000)

출력

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

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

---

사용할 자료구조

문제에서 원을 이루며 앉아있다 언급했기 때문에 맨앞(front)와 맨뒤(back)가 연결되게끔 구현할 수 있는 Queue를 사용했습니다.

풀이 과정

1. 1부터 입력받은 N까지를 미리 Queue에 삽입해두었습니다.

2. 사람들이 모두 제거될 때까지 계속 삭제 연산을 반복해야하므로 while(!q.empty()) 만큼 루프를 돕니다.

3. 만약 K가 3이라면, 3번째 사람을 제거해야하므로 2번 회전을 시키고 3번째 나오는 수를 삭제합니다. ⇒ 즉, K-1 만큼 루프를 돌며 맨 앞에 있는 숫자를 맨 뒤로 보냅니다.

for(int i=0;i<k-1;i++){ q.push(q.front()); q.pop(); }

1. pop할 숫자를 먼저 형식에 맞춰 출력해주고 pop 연산을 해주면 됩니다.

시간 복잡도

Queue의 삽입/삭제 연산의 시간 복잡도는 O(1)

N개의 숫자를 반복을 돌며 K번 순회하므로 O(N*K) 이다.

#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <stack> #include <queue> #include <map> #include <functional> using namespace std; int main(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n,k; queue<int> q; cin>>n>>k; for(int i=1;i<=n;i++){ q.push(i); } cout<<"<"; while(!q.empty()){ for(int i=0;i<k-1;i++){ q.push(q.front()); q.pop(); } if(q.size()==1){ cout<<q.front()<<">"; }else{ cout<<q.front()<<", "; } q.pop(); } }