[BOJ] 1158 요세푸스 문제 - 이중 연결 리스트(Doubly Linked List), 큐(Queue) 구현

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

 

 

이중 연결 리스트(Doubly Linked List) 소스 코드:

#include <iostream>
using namespace std;

int n, k;

class linkedlist {
public:
	class node {
	public:
		int num;
		node *right;
		node *left;

		node(int n) {
			num = n;
			left = NULL;
			right = NULL;
		}
	};
	node *head;

	void insert() {
		head = new node(1);

		node *cur = head;
		for (int i = 2; i <= n; i++) {
			node *newone = new node(i);
			cur->right= newone;
			newone->left = cur;
			cur = newone;
		}
		cur->right = head;
		head->left = cur;
	}
	void print() {
		int cnt = n;
		node * cur = head;
		cout << "<";
		while (cnt) {
			for (int i = 0; i < k-1; i++) {
				cur = cur->right;
			}
			cnt--;
			cout << cur->num;
			if (cnt) cout << ", ";
			cur->left->right = cur->right;
			cur->right->left = cur->left;
			cur = cur->right;
		}
		cout << ">";
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	linkedlist *list = new linkedlist();

	cin >> n >> k;

	list->insert();
	list->print();

	return 0;
}

 

큐(Queue) 소스 코드:

#include <iostream>
#define QSIZE 5500
using namespace std;

int n, k;
int q[QSIZE],f,r;

void insert(int num) {
	q[r] = num;
	r = (r + 1) % QSIZE;
}
void pop() {
	f = (f +1) % QSIZE;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> k;

	for (int i = 1; i <= n; i++) insert(i);

	cout << "<";
	while (n) {
		for (int i = 0; i < k-1; i++) {
			insert(q[f]);
			pop();
		}
		n--;
		cout << q[f];
		pop();
		if (n) cout << ", ";
	}
	cout << ">";
	return 0;
}