백준 11866: 요세푸스 문제0(C언어)

11866번: 요세푸스 문제 0

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다.

한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.

이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

문제풀이

위의 내용을 정리해보면

1. N과 K를 입력받는다.

2. N개만큼 큐에 1부터 N까지 저장한다.

3. K번째의 숫자를 출력하고 제거한다.

4. 첫번째 순서는 K+1번째의 숫자부터 다시 시작한다.

5. 3번과 4번을 반복한다.

 

정리한 바탕의 내용으로 두 가지의 방법으로 풀었다.

큐에 가까운 방식은 2번째 방법이 큐에 가깝고, 메모리는 둘다 1116KB인데 코드1은 4ms이고, 코드2는 0ms이였다.

첫번째는 단순히 1차원 배열에 미리 1부터 N번째까지의 값을 1로 저장을 해주고, K번째의 배열마다 0으로 값을 바꿔서

방문을 했었는지 체크해줬다. K번째의 숫자인지는 배열의 값이 1이면 카운트해주는 것으로 만들었다.

그렇게 계속해서 출력을 하다가 출력한 숫자의 개수와 N의 값이 같다면 반복문을 종료해줬다.

아래의 코드가 위의 방법을 활용해서 만든 방법이다.

최종코드1

#include<stdio.h>

int arr[1001];
int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		arr[i] = 1;
	}
	printf("<");
	int idx = 1;
	int ncount = 0, cnt = 0;
	while (1) {
		if (arr[idx] == 1) cnt++;
		if (arr[idx] == 1 && cnt == k) {
			cnt = 0;
			arr[idx] = 0;
			ncount++;
			if (ncount == n) {
				printf("%d>", idx);
				break;
			}
			printf("%d, ", idx);
		}
		idx++;
		if (idx > n) idx = idx - n;
	}
	return 0;
}

---

두번째 방법은 해싱을 활용해서 만든 큐이다.

push로 먼저 1부터 N번째까지의 값을 해시테이블에 저장을 해줬다.

Key 값으로는 어차피 숫자는 겹치지 않고 고유한 속성이기 때문에 숫자 자체를 키 값으로 줬다.

pop함수로 K번째 숫자 노드와의 연결을 앞, 뒤 노드와 끊어주면서 그 노드의 값을 출력해주고,

hashTable의 head가 가르키는 부분을 다음 노드로 해줬고,. K번째의 숫자이기 때문에 현재 위치의

개수도 세주기 위해서 노드의 이동은 2번만 해줬다. 해싱에 대한 자세한 설명은 블로그에 올라와 있다.

최종코드2

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

int n, k;
struct bucket* hashTable = NULL;

struct node {
	int key;
	struct node* next;
	struct node* previous;
};

struct bucket {
	int count;
	struct node* head;
};

struct node* createNode(int key) {
	struct node* newNode;
	newNode = (struct node*)malloc(sizeof(struct node));
	newNode->key = key;
	newNode->previous = NULL;
	newNode->next = NULL;
	return newNode;
}

void push(int key) {
	struct node* newNode = createNode(key);
	struct node* node = hashTable->head;
	if (hashTable->count == 0) {
		hashTable->count = 1;
		hashTable->head = newNode;
		newNode->previous = hashTable->head;
		newNode->next = hashTable->head;
	}
	else {
		hashTable->count++;
		node->previous->next = newNode;
		newNode->previous = node->previous;
		node->previous = newNode;
		newNode->next = node;
	}
	return;
}

int pop() {
	struct node* node = hashTable->head;
	for (int i = 1; i < k; i++) {
		node = node->next;
	}
	if (hashTable->count > 0) hashTable->count--;
	hashTable->head = node->next;
	node->previous->next = node->next;
	node->next->previous = node->previous;
	int ans = node->key;
	free(node);
	return ans;
}

int main() {
	scanf("%d %d", &n, &k);
	hashTable = (struct bucket*)malloc(sizeof(struct bucket));
	hashTable->count = 0;
	hashTable->head = NULL;
	for (int i = 1; i <= n; i++) {
		push(i);
	}
	printf("<%d", pop());
	for (int i = 1; i < n; i++) {
		printf(", %d", pop());
	}
	printf(">");
	free(hashTable);
	return 0;
}