[C언어] 백준 1158번 조세퍼스 문제

*이 포스트에서 문제의 답안은 C언어로 구성했습니다.

#include <stdio.h>
#include <stdlib.h>

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _CLL
{
	Node * tail;
	Node * cur;
	Node * before;
	int numOfData;
} CList;

typedef CList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);
void LInsertFront(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
Data LRemove(List * plist);
int LCount(List * plist);

void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->tail == NULL)
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
	}

	(plist->numOfData)++;
}

void LInsert(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->tail == NULL)
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}

	(plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
	if (plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->tail-1;
	plist->cur = plist->tail;

	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if (plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data rdata = rpos->data;

	if (rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if (plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

int LCheck(List * plist)
{	
	if (plist->tail == NULL)
		return 0;
	if (plist->tail != NULL)
		return 1;
}

int main(void) {
	List list;
	int n, k, count;
	int data;
	ListInit(&list);

	scanf_s("%d %d", &n, &k);

	for (int i = 1; i <= n;i++)
	{ LInsert(&list,i ); 
	}

	LFirst(&list, &data);
	printf("<");
	do{
		   for (int i = 0; i < k;i++)
			{
				LNext(&list, &data);
			}
			printf("%d", data);
			LRemove(&list);
			count = LCheck(&list);
			if (count == 0)break;
			printf(", ");
	} while (count != 0);
	printf(">");

	}

알아야 하는 함수 및 코드
printf
scanf
for
do while
조건연산자
연결리스트

조세퍼스의 원리 
처음 문제를 읽으면 무슨 소리인가 싶은데 예제를 써보면서 원리를 이해하면 된다.
입력 : 7 3  
7명 / 원형 3번째 자리 사람 제거
1 2 3 4 5 6 7 -> 3
4 5 6 7 1 2 -> 6
7 1 2 4 5 -> 2
4 5 7 1 -> 7
1 4 5 -> 5
1 4 -> 1        세 번째가 없고 원이므로 순환해서 3번째 인 대상이 선택된다. 즉 1 4 1. 
4 -> 4           하나밖에 없으므로 그 하나가 순환 후의 세번째이다. 4 4 4.
출력 <3, 6, 2, 7, 5, 1, 4>
핵심은 3번째가 제거된 그 자리부터 순환이 반복된다는 것이다.