[1158] 요세푸스 - 큐, 연결 리스트 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

---

[ 문제 접근 ]

 

- 요세푸스 문제라는 유명한 문제인데, 처음 보고는 어떻게 풀어야할지 감이 안잡혔다.

 

컨셉만 알면 구현은 쉬운데 컨셉을 생각하기까지 버벅거렸다.

 

1.Queue 를 이용하거나 2.Circular Linked List 를 사용하거나 3.Recursion 으로 풀 수 있다.

---

[ 최종 코드 ]

 

#include<iostream>
#include<queue>
 
using std::cout; using std::cin;
 
int n, k;
 
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
 
	cin >> n >> k;
	
	std::queue<int> que;
    
	for (int i = 1; i <= n; i++) {
		que.push(i);
	}
    
	cout << "<";
	while (!que.empty()) {
		for (int i = 0; i < k-1; i++) {
			int cur = que.front();
			que.pop();
			que.push(cur);
		}
		if (que.size() == 1) cout << que.front();
		else { cout << que.front() << ", " ; }
		que.pop();
	}
	cout << ">";
	
	return 0;
}

 

[ Queue 를 이용한 비슷한 코드 ]

 

#include<iostream>
#include<queue>
 
using namespace std;
 
void josephus(int n, int k) {
	queue<int> survivors;
	int* arr = new int[n];
 
	for (int i = 1; i <= n; ++i) survivors.push(i);
 
	int cnt = 1; // 사람 카운트
	int i = 0; // 배열 idx
	while (!survivors.empty()) {
 
		if (cnt == k) {
			arr[i++] = survivors.front(); // arr 배열에 저장.
			survivors.pop();
			cnt = 1;
		}
		else {
			survivors.push(survivors.front());
			survivors.pop();
			cnt++;
		}
	}
 
	// arr를 이용해서 range based for문 사용하려고 했는데
    // 동적할당한 arr는 range based for loop을 사용할수 없다. ===> vector를 애용하자!!
	cout << "<";
	for (int i = 0; i < n-1; i++) {
		cout << arr[i] << ", ";
	}
	cout << arr[n - 1] << ">";
 
}
 
 
int main() {
	
	int k, n;
	cin >> n >> k;
 
	josephus(n, k);
 
	return 0;
}

---

[ 원형 리스트를 컨셉을 이용한 방법 ]

 

#include<iostream>
#include<algorithm>
#include<vector>
 
 
using std::cout; using std::cin;
using std::vector;
 
int n, k;
 
int pre[5001];
int next[5001];
 
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
 
	vector<int> vec; // 요세푸스 순열 저장할 변수.
	cin >> n >> k;
	
	// 원형 연결 리스트 생성
	// 맨 처음 노드와 마지막 노드가 서로를 가리키도록.
	for (int i = 1; i <= n; i++) {
		pre[i] = (i == 1) ? n : i - 1;
		next[i] = (i == n) ? 1 : i + 1;
	}
 
	int size = n;
	int cnt = 1;
	for (int cur = 1; size != 0; cur = next[cur]) {
		if (cnt == k) {
			// 제거 ( 실제 제거는 안하지만 값 인덱싱 못하게 끔 )
			pre[next[cur]] = pre[cur];
			next[pre[cur]] = next[cur];
			vec.push_back(cur);
			cnt = 1;
			--size;
		}
		else {
			cnt++;
		}
	}
 
	cout << "<";
	for (size_t i = 0; i < vec.size(); ++i) {
		cout << vec[i];
		if (i != vec.size() - 1) cout << ", ";
	}
	cout << ">";
 
	return 0;
}

---

[ Key Point ]

 

 

---

[ 다른 사람 풀이 ]