[백준] 1158번 요세푸스 문제

문제

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

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 ≤ 5,000)

출력

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

---

풀이

링크드 리스트를 이용해서 원형 큐를 만들었다. 그리고 head가 NULL이 될 때 까지 계속 돌려준다.

#include <stdio.h>
#include <stdlib.h>
struct node { int key; struct node* next; }; 

struct node* head=NULL;


void in(int key) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->key = key;

    struct node* ptr = head;

    if (head == NULL) {
        head = newnode;
        newnode->next = newnode;
    }
    else {
        while (ptr->next != NULL && ptr->next != head) { ptr = ptr->next; }
        ptr->next = newnode;
        newnode->next = head;
    }
}

void out(struct node* ptr) {
    printf("%d", ptr->key);
    struct node* newptr = head;

    if (head->key == ptr->key && head->next == head) {
        head = NULL;
        return;
    }

    while (newptr->next->key != ptr->key)newptr = newptr->next;
    if (head->key == ptr->key) head = ptr->next;
    newptr->next = ptr->next;
    free(ptr);
}

int main(void) {
    int n, k;
    scanf("%d %d", &n, &k);

    for (int i = 1; i <= n; i++) {
        in(i);
    }
    int check = 0;
    int once = 1;
    struct node* run = head;
    printf("<");
    while (head != NULL) {
        check++;
        if (check%k == 0 && check != 0) {
            if (once != 1) {
                printf(", ");
            }
            else once = 0;

            struct node* ptr = run;
            run = run->next;
            out(ptr);
        }
        else {
            run = run->next;
        }
    }
    printf(">");
}

그새 링크드 리스트 만드는 법 까먹어서 2학기에 수업했던 코드를 확인하고 왔다.

출력할 때, ', '을 맨 처음과 끝에는 출력하지 않아야 하는데 처음에는 출력을 안하고, 그 다음부터는 숫자가 나오기 전에 출력하게 하면서 맨 마지막에는 들어가지 않게 했다.

또, count를 셀 때 out(), check++, run=run->next의 순서를 잘 조절해 줘야겠다.