07.02. 요세푸스 문제 [Linked List][백준 1158]

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

1158번: 요세푸스 문제

 

Algorithm classification : Linked List, Data Structure, Queue

 

07.02.1. Problem

The Josephus problem is:

N people from 1 to N sit in a circle and are given a positive integer K (≤ N). Now remove the Kth person in order. When one person is eliminated, the process continues along the circle of the remaining ones. This process continues until all N people have been eliminated. The order in which people are removed from the circle is called the (N, K)-Josephus permutation. For example, the (7, 3)-Josephus permutation is <3, 6, 2, 7, 5, 1, 4>.

Write a program to find the (N, K)-Josephus permutation given N and K.

 

 

07.02.2. Input limit

In the first line, N and K are given in order with a blank space in between. (1 ≤ K ≤ N ≤ 5,000)

 

07.02.3. Output

Print the Josephus permutation as in the example.

 

07.02.4. Solution

Circular linked list와 Doubly linked list를 구현하는 대표적인 문제입니다. 유명한 문제라서 마주친 적이 있는 분들도 많으실 것 같습니다. 시간복잡도도 생각해보면 매번 삭제당하는 번호를 순서대로 따라가는 것을 고려하여 O(NM)임을 알 수 있습니다.

 

이전에 소개해드린 문제와 마찬가지로 천천히 작성해보시면 됩니다.

typedef struct node {
   int dataPtr;
   struct node* next;
} NODE;
typedef struct {
   NODE* front;
   NODE* rear;
   int count;
} QUEUE;

 

이참에 queue의 기초적인 함수들을 다 구현해봐도 좋겠네요.

QUEUE* createQueue(int k){
	QUEUE *pNewQueue = (QUEUE*)malloc(sizeof(QUEUE));
	if(pNewQueue == NULL)
		return NULL;
	pNewQueue->count = 0;
	pNewQueue->front = pNewQueue->rear = 0;
	return pNewQueue;
}
bool enqueue(QUEUE* queue, int item){
	NODE *pNewNode = (NODE*)malloc(sizeof(NODE));
	
	pNewNode->dataPtr = item;
	pNewNode->next = NULL;
	
	if(queue->count <= 0){
		queue->front = queue->rear = pNewNode;
	}
	else{
		queue->rear->next = pNewNode;
		queue->rear = pNewNode;
	}
	queue->count++;
	return true;
}
int dequeue(QUEUE* queue){
	NODE *pOldNode = (NODE*)malloc(sizeof(NODE));
	if(queue->count == 0)
		return 0;
	int item;
	pOldNode = queue->front;
	item = pOldNode->dataPtr;
	
	if(queue->count == 1){
		queue->front = queue->rear = NULL;
	}
	else{
		queue->front = pOldNode->next;
	}
	free(pOldNode);
	queue->count--;
	return item;
}
int queueFront(QUEUE* queue){
	if(queue->count == 0)
		return 0;
	return queue->front->dataPtr;
}
int queueRear(QUEUE* queue){
	if(queue->count == 0)
		return 0;
	else
		return queue->rear->dataPtr;
}
bool emptyQueue(QUEUE* queue){
	if(queue->count == 0)
		return true;
	return false;
}
int queueCount(QUEUE* queue){
	return queue->count;
}
void destroyQueue(QUEUE* queue){
	NODE *pOldNode = (NODE *)malloc(sizeof(NODE));
	while(queue->count){
		pOldNode = queue->front;
		queue->front = pOldNode->next;
		free(pOldNode);
		queue->count--; 
	}
	free(queue);
}