[백준(BOJ) / C][Silver Ⅳ] 1158번 : 요세푸스 문제

문제

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

1158번: 요세푸스 문제

---

풀이

이 문제는 원형 링크드 리스트를 사용하여 문제를 해결하였습니다.

리스트에 1,2,3,4 ... N 의 숫자를 넣은 후 K 만큼 옆으로 이동하여 그 숫자를 출력하고 리스트에서 제외한다.

이 행동을 리스트에 숫자가 다 없어질때까지 반복한다.

 

배열을 사용하여 해당 값을 넣은 뒤 for문으로 풀게되면 원형 링크드 리스트를 사용하는 것보다 시간이 3배 넘게 오래 걸리기때문에 효율적이지 못하다.

 

그러기에 큐(Queue)를 이용하거나 원형 링크드 리스트를 사용하는 것이 효율이 좋다.

---

소스코드

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

typedef struct tag_Node
{
	int data;
	
	struct tag_Node* prevNode;
	struct tag_Node* nextNode;
}Node;

Node* CreateNode(int NewData);
void AppendNode(Node** Head, Node* NewNode);
void RemoveNode(Node** Head, Node* Remove);
Node* Shift(Node* Current, int Location);
void DestroyNode(Node* Node);
int GetNodeCount(Node* Head);

int main(void)
{
	int n,k,count;
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;
	
	scanf("%d %d", &n, &k);
	
	// 리스트에 N개의 숫자를 오름차순으로 입력
	for(int i = 0; i < n; i++)
	{
		NewNode = CreateNode(i+1);
		AppendNode(&List, NewNode);
	}
	
	// 만약 숫자가 1이라면 출력할 숫자도 1뿐이기에 1만 출력 후 종료 
	if(n == 1)
	{
		printf("<1>");
		return 0;
	}
	
	// 첫 번째 출력 후 노드 삭제
	Current = Shift(List, k-1);

	RemoveNode(&List,Current);
	printf("<%d, ", Current->data);
	
	// 첫번째, 마지막 노드를 따로 출력하니 두개를 빼고 나머지를 계산
	for(int j = 0; j < n-2; j++)
	{
		Current = Shift(Current, k);
		printf("%d, ", Current->data);
		RemoveNode(&List, Current);
	}
	
	// 마지막 출력 후 노드 삭제
	Current = Shift(List, k);
	RemoveNode(&List,Current);
	printf("%d>", Current->data);
	
	count = GetNodeCount(List);
	
	for(int i = 0; i < count; i++)
	{
		Current = Shift(List, 0);
		
		if(Current != NULL)
		{
			RemoveNode(&List, Current);
			DestroyNode(Current);
		}
	}
	
	return 0;
}

// 노드 생성
Node* CreateNode(int NewData)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	
	NewNode->data = NewData;
	NewNode->nextNode = NULL;
	NewNode->prevNode = NULL;
	
	return NewNode;
}

// 현재 가르키고있는 노드를 K 만큼 이동.
Node* Shift(Node* Current, int Location)
{
	Node* CurrentNode = Current;
	while(CurrentNode != NULL && (--Location) >= 0)
	{
		CurrentNode = CurrentNode->nextNode;
	}
	
	return CurrentNode;
}

// 리스트에 노드를 추가
void AppendNode(Node** Head, Node* NewNode)
{
	if(*Head == NULL)
	{
		*Head = NewNode;
		(*Head)->nextNode = *Head;
		(*Head)->prevNode = *Head;
	}
	else
	{
		Node* TailNode = (*Head)->prevNode;
		
		TailNode->nextNode->prevNode = NewNode;
		TailNode->nextNode = NewNode;
		
		NewNode->nextNode = (*Head);
		NewNode->prevNode = TailNode;
	}
}
// 동적할당된 노드 메모리 해제
void DestroyNode(Node* Node)
{
	free(Node);
}

// 출력한 노드는 리스트에서 삭제
void RemoveNode(Node** Head, Node* Remove)
{
	
	if((*Head) == Remove)
	{
		(*Head)->prevNode->nextNode = (*Head)->nextNode;
		(*Head)->nextNode->prevNode = (*Head)->prevNode;
		
		(*Head) = Remove->nextNode;	
	}
	else
	{
		Remove->prevNode->nextNode = Remove->nextNode;
		Remove->nextNode->prevNode = Remove->prevNode;
	}
}

// 리스트의 총 노드 개수를 구함
int GetNodeCount(Node* Head)
{
	unsigned int Count = 0;
	Node* Current = Head;
	
	while(Current != NULL)
	{
		Current = Current->nextNode;
		Count++;
			
		if(Current == Head)
		{
			break;
		}
	}
	
	return Count;
}