백준_11866_요세푸스문제0

 

사람 명수를 의미하는 N 과

몇 번째를 의미하는 K 를 입력받아서 요세푸스 순열을 구하는 문제입니다.

 

사람들이 둘러앉아있는 모양이기 때문에, 원형 큐의 성질을 이용하면 풀 수 있을 것이라는 생각이 듭니다.

 

그런데, 큐는 FIFO (먼저 들어간게 먼저 나오는 성질) 을 가지고 있지만, 

 

이 문제에서는 K번째 사람을 제거해야 하므로, pop 함수를 조금 다르게 구현해야 할 것 같습니다.

 

 

 

POP 함수)

 

조건 1 : 큐의 모든 값이 빠져나가면 pop을 할 수 없다.

 

조건 2 : K번째 사람을 제거하려 했을 떄 그 자리가 이미 공석이라면, 공석이 아닐 때까지 이동한다.

 

int pop(int n, int k)
{
    int t = 0;
    t = queue[front];
    queue[front] = 0;

    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (queue[i] != 0)
        {
            j = 1;
            break;
        }
    }
    if (j == 0)
    {
        return t;
    }

    for (int i = 0; i < k; i++)
    {
        front++;
        front %= n;

        while (1)
        {
            if (queue[front] == 0)
            {
                front++;
                front %= n;
            }
            else
            {
                break;
            }
        }
    }

    return t;
}

 

첫 번째 for 문을 통해 조건 1을,

두 번째 for 문을 통해 조건 2를 만족시키는 pop 함수를 만들었습니다.

 

push 함수는 일반적인 큐 형태와 같고

 

main함수에서는 결과값만 나오게 해주면 됩니다

 

 

 

 

전체 코드)

#include <stdio.h>

#define N 1001

int queue[N];
int front = 0, rear = 0;

int push(int k);
int size();
int pop(int n, int k);

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

    for (int i = 0; i < n; i++)
    {
        push(i + 1);
    }
    int s = size();

    front = k - 1;
    int result[n];

    for (int i = 0; i < s; i++)
    {
        result[i] = pop(n, k);
    }

    printf("<%d", result[0]);

    for (int i = 1; i < n; i++)
    {
        printf(", %d", result[i]);
    }
    printf(">\n");

    return 0;
}

int push(int k)
{

    if ((rear + 1) % N == front % N)
    {
        return -1;
    }
    else
    {
        queue[rear] = k;
        rear++;
        rear %= N;
        return 1;
    }
}

int size()
{
    int size = 0;
    for (int i = front; i < rear; i++)
    {
        size++;
    }
    return size;
}

int pop(int n, int k)
{
    int t = 0;
    t = queue[front];
    queue[front] = 0;

    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (queue[i] != 0)
        {
            j = 1;
            break;
        }
    }
    if (j == 0)
    {
        return t;
    }

    for (int i = 0; i < k; i++)
    {
        front++;
        front %= n;

        while (1)
        {
            if (queue[front] == 0)
            {
                front++;
                front %= n;
            }
            else
            {
                break;
            }
        }
    }

    return t;
}