[자료구조] 해적 널빤지 사형에서 살아남기 (queue)

교재 : C로 배우는 쉬운 자료구조

문제 : Chapter 06 - 응용예제 07 - 해적 널빤지 사형에서 살아남기

구분 : 원형 큐(circle queue)

 

 

<문제풀이>

/*보안자료구조
응용예제 07, 해적 널빤지 사형에서 살아남기

<입출력 예제>
7 3 -> 3 6 2 7 5 1 4
10 4 -> 4 8 2 7 3 10 9 1 6 5
*/
#include <stdio.h>
#define MAX 100  // 1<=n<=50 이므로, 널널하게 100
int front = 0; // 초기 front와 rear은 0으로 초기값 셋팅
int rear = 0;
int queue[100];

int IsEmpty(void) {     // 원형 큐의 front와 rear이 같다면, 원형 큐는 비어있는 상태.
    if (front == rear)
        return 1;
    else return 0;
}

int IsFull(void) {                  // 원형 큐의 front와 (rear+1)%MAX의 값이 같다면, rear이 한바퀴 돌아서 front와 같아진 것 이므로 full이다.
    if (front == (rear + 1) % MAX)  // front와 rear은 삽입과 삭제 시 mod 연산을 통해 값을 다시 넣어주기 때문에 이 부분에서 mod연산을 할 필요가 없다.
        return 1;                   // 하지만, rear이 큐 마지막 공간에서 +1 되었을 때, index 참조 에러가 날 수 있으므로, (rear+1)%MAX로 mod 연산을 수행한다.
    else
        return 0;
}

void add(int value) {   // 큐에 값을 삽입하는 함수
    if (IsFull()==1)
        printf("Queue is full.\n");
    else {
        rear = (rear + 1) % MAX;    // 현재 rear값에서 한칸 앞에 있는 index를 지정해준다. 최대 index 이후, 다시 queue[0]으로 연결하기 위해서 mod 연산을 수행한다.
        queue[rear] = value;        // 값 삽입.
    }

}
int delete() {          // 큐에 값을 삭제하는 함수
    if (IsEmpty()==1)
        printf("Queue is empty.\n");
    else {
        front = (front + 1) % MAX;  // front값에서 한칸 앞에 있는 index를 지정해준다. 최대 index 이후, 다시 queue[0]으로 연결하기 위해서 mod 연산을 수행한다.
        return queue[front];        // 값 삭제.
    }
}

int main() {
    int n, k, tmp;
    scanf_s("%d %d",&n, &k);
    for (int i = 1; i <= n; i++)  add(i);   //1부터 n까지 숫자 순서대로 삽입.
    while (IsEmpty() != 1) {                //queue가 모두 비어있다면 while문 탈출.
        for (int i = 0; i < k - 1; i++) {   //k-1번만큼 front값을 이용해서 delete 함수로 값을 삭제하고, 다시 큐의 rear을 이용해서 add 함수로 값 삽입.
            tmp = delete();
            add(tmp);
        }
        printf("%d ", delete());            //k번째 값을 queue에서 삭제하면서 출력.
    }
    return 0;
}