[BaekJoon/백준] 11866번 큐 활용(요세푸스 문제)

이 문제를 큐로 끌어내는 데에만 시간이 좀 걸렸다.

 

N = 7, K = 3이라고 보자.

 

1 2 3 4 5 6 7

 

1부터 시작하여 세번째는 3

1 2 3 4 5 6 7

<3, 

 

4부터 시작하여 세번째는 6

1 2 4 5 6 7 

<3, 6

 

7부터 시작하여 세번째는 2

1 2 4 5 7

<3, 6, 2

 

4부터 시작하여 세번째는 7

1 4 5 7

<3, 6, 2, 7

 

1부터 시작하여 세번째는 5

1 4 5

<3, 6, 2, 7, 5

 

1부터 시작하여 세번째는 1

1 4

<3, 6, 2, 7, 5, 1,

 

4부터 시작하여 세번째는 4

4

<3, 6, 2, 7, 5, 1, 4>

 

 

스택은 앞에서부터 빼내는건데, 세번째를 어떻게뽑아? 

라고 생각할 수 있다.

 

그럼 세번째까지 모두 뽑으면 된다.

 

 

1 2 3 4 5 6 7

여기서

 

1을 디큐하고 인큐하면

2 3 4 5 6 7 1

 

2를 디큐하고 인큐하면

3 4 5 6 7 1 2

 

이러고 3을 디큐하면 된다.

 

즉, K - 1회 "인큐 - 디큐" 해준 뒤, 한번 더 디큐 한 값이 요세푸스 순열의 멤버가 된다. 

 

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

// 링 버퍼 구조로 큐를 구현
typedef struct {
    int max; //  큐의 용량
    int num; // 현재 데이터 수. front와 rear의 값이 같은 경우 큐가 비어있는지, 가득찼는지 구별할 수 없는 상황을 피하기 위해 사용.
    int front; // 프런트. 첫 번째 요소의 인덱스를 저장
    int rear; // 리어. 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장 (다음 인큐 시에 데이터가 저장될 요소의 인덱스를 미리 준비하는 것)
    int *que; // 큐의 첫 요소에 대한 포인터
} IntQueue;

int Initialize(IntQueue *q, int max) {
    q->num = q->front = q->rear = 0; // 모두 0
    if((q->que = calloc(max, sizeof(int))) == NULL) {
        q->max = 0;
        return -1; // 실패
    }
    
    q->max = max;
    return 0; // 성공
}

int Enque(IntQueue *q, int x) {
    
    if(q->num >= q->max) {
        return -1;
    }
    
    q->num++;
    q->que[q->rear++] = x;
    
    q->rear = q->rear % q->max;
    // 그냥 q->rear == q->max 일 때, q->rear = 0 해줘도 됨.
    
    return 0;
    
}

int Deque(IntQueue *q, int *x) {
    
    if(q->num <= 0) {
        *x = -1;
        return -1;
    }
    
    q->num--;
    *x = q->que[q->front++];
    
    q->front = q->front % q->max;
    // 그냥 q->front == q->max 일 때, q->front = 0 해줘도 됨.

    
    return 0;
    
}

int Size(IntQueue *q) {
    return q->num;
}

int IsEmpty(IntQueue *q) {
    return (q->num <= 0);
}

int Front(IntQueue *q) {
    if(q->num == 0)
        return -1;
    
    return q->que[q->front];
}

int Back(IntQueue *q) {
    if(q->num <= 0)
        return -1;
    
    return q->que[q->rear - 1];
}

int N, K;
int arr[1000];
int iter; // arr iterator

int main() {
    int input;
    IntQueue que;
    
    scanf("%d %d", &N, &K);
    Initialize(&que, N);
    
    for(int i = 1; i <= N; i++) {
        
        Enque(&que, i);
        
    }
    
    input = Front(&que);
    while(!IsEmpty(&que)) {
        
        for(int i = 0; i < K - 1; i++) {
            Deque(&que, &input);
            Enque(&que, input);
        }
        
        Deque(&que, &input);
        arr[iter++] = input;
    }
    
    printf("<");
    for(int i = 0; i < iter; i++) {
        printf("%d", arr[i]);
        
        if(i != iter - 1) // 마지막이 아닌 경우 추가.
            printf(", ");
    }
    printf(">");
    
}