[백준1158]조세퍼스문제 -연결리스트로 구현해보기

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

1158번: 조세퍼스 문제

 STL Que를 써서 구현할수도 있지만, que를 직접 구현해보면서 풀기에 좋은문제라고 생각한다

 

 

#include<iostream>
using namespace std;
#define INF 987654321
struct Node {
	int data;
	struct Node *next;
};
struct LinkedQueue {
	Node *front, *rear;
	int len=0;
	LinkedQueue() //구조체의 초기값 정하기 
	{
		front == rear == NULL; //처음에 가리키는 노드 없으니까 null
	}
	int size() {
		return len;
	}
	bool isEmpty() {
		return len == 0; //len이 0일때만 참 반환
	}
	void enqueue(int data)
	{
		Node *node = (Node*)malloc(sizeof(Node));
		node->data = data;
		node->next = NULL;
		if (isEmpty())
		{
			front = rear = node; 
		}
		else
		{
			rear->next = node;//꼬리에 새로운 노드연결시켜주고
			rear = rear->next;//꼬리로 이동
		}
		len++;//큐증가
	}
	int deque() {
		if (isEmpty())
		{
			printf("Q is Empty\n");
			return INF;
		}
		Node *delnode = front;
		int ret = delnode->data;
		front = delnode->next;
		free(delnode);
		len--;
		return ret;
	}
	int isfront()
	{
		return front->data;
	}
};
int main()
{
	int N, K;
	LinkedQueue que;
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++)
	{
		que.enqueue(i);
	}
	printf("<");
	while (!que.isEmpty())
	{
		for (int i = 0; i < K-1; i++)
		{
			if (!que.isEmpty())
			{
				int temp = que.deque();
				que.enqueue(temp);
			}
		}
		int ans = que.deque();
		if (que.size() ==0)
		{
			printf("%d", ans);
		}
		else
		printf("%d, ", ans);
	}
	printf(">");
}