[Jungol] 정올 3101 요세푸스 문제 1

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2370&sca=50&sfl=wr_homepage&stx=comkiwer

Approach

N명이 원형으로 모여 앉아 있을 때, 기준으로 부터 시작하여 K번째 사람을 모임에서 제외한다.

이를 N번 실행한 경우 제외된 사람을 순차적으로 나열한 순열을 요세푸스(Josephus) 순열이라고 한다.

 

배열에서 K번째 원소를 찾은 후, 제거된 순서대로 Queue에 넣어줍니다.

K 번째 원소를 찾을 때 사용하는 배열을 원형 큐 구조로 구현

 

▶  [큐] Queue란? 

[큐] Queue란?

 

방법 1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
const int LM = 10005;
int N, K;
int queue[LM];
int sp, ep;
typedef struct _List {
    struct _Node* cur;
    struct _Node* head;
    struct _Node* tail;
}LL;
 
typedef struct _Node {
    int data;
    struct _Node* next;
}Node;
 
void createNode(LL *L, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
 
    // 기존에 데이터가 없었던 경우
    // head와 tail의 next는 다시 자기 자신을 가리킴
    if (L->head == NULL && L->tail == NULL) {
        L->head = L->tail = newNode;
        newNode->next = newNode;
    }
 
    else { // 기존 데이터 존재할 때
        L->tail->next = newNode;
        L->tail = newNode;
        // 원형이기 때문에 마지막 노드와 시작 노드 연결
        newNode->next = L->head;
        // L->tail->next = L->head;
    }
}
 
void process(LL *L) {
    Node *pre, *cur;
    pre = cur = L->head;
 
    int cnt = 0;
    int size = N;
    while (size > 0) {
        // K만큼 이동
        cnt = K;
        while (--cnt) {
            pre = cur;
            cur = cur->next;
        }
 
        // 큐에 삭제할 데이터 저장
        queue[ep++] = cur->data;
        // K번째가 시작 노드인 경우
        if (cur == L->head) {
            L->head = cur->next;
            L->tail->next = cur->next;
        }
        // K번째가 마지막 노드인 경우
        else if (cur == L->tail) {
            L->tail = pre;
        }
 
        pre->next = cur->next;
        pre = cur;
        cur = cur->next;
        size--;
    }
}
 
// 모든 데이터 삭제
void deleteNode(LL *L) {
    Node* cur = L->head;
    Node* tmp;
    while (cur != L->tail) {
        tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    free(cur);
    L->head = NULL;
    L->tail = NULL;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    LL* L = (LL*)malloc(sizeof(LL));
    L->cur = NULL;
    L->tail = NULL;
    L->head = NULL;
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        createNode(L, i);
    }
 
    process(L);
 
    for (int i = 0; i < ep; i++) {
        printf("%d ", queue[i]);
    }
 
    // 메모리 해제
    deleteNode(L);
    return 0;
}

---

방법 2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 10004;
struct Node {
    int data;
    Node* next;
    Node* alloc(int nd, Node* np) {
        data = nd, next = np;
        return this;
    }
}buf[LM];
int bcnt;
 
struct CircularQueue {
    Node* head;
    int cnt;
    void init() {
        cnt = bcnt = 0;
        head = NULL;
    }
    
    bool empty() { return cnt == 0; }
    int size() { return cnt; }
    int top() { return head->next->data; }
    void push(int num) {
        cnt++;
        // 기존에 데이터가 없었던 경우
        if (head == NULL) { 
            head = buf[bcnt++].alloc(num, NULL);
            head->next = head;
        }
        // 기존에 데이터가 있는 경우
        else {
            head->next = buf[bcnt++].alloc(num, head->next);
            head = head->next;
        }
    }
    void pop() {
        // 큐가 비워진 경우
        if (cnt == 0)
            return;
        // 원소가 1개인 경우
        if (cnt == 1) head = NULL;
        else head->next = head->next->next;
        cnt--;
    }
    void move() {
        head = head->next;
    }
}cque;
 
int main() {
    // freopen("input.txt", "r", stdin);
    int N, K, i, j, cnt;
    cque.init();
    scanf("%d %d", &N, &K);
    for (i = 1; i <= N; ++i) {
        cque.push(i);
    }
    
    for (i = 0; i < N; ++i) {
        for (j = 1; j < K; ++j) {
            cque.move();
        }
        printf("%d ", cque.top());
        cque.pop();
    }
}