백준 2164번 : 카드2 [C]

주소 : https://www.acmicpc.net/problem/2164

2164번: 카드2

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MAX_QUEUE_SIZE 500001
typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
}QueueType;

void init_queue(QueueType* q)
{
	q->front = q->rear = 0;
}

int is_empty(QueueType* q)
{
	return(q->front == q->rear);
}

int is_full(QueueType* q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void enqueue(QueueType* q,element item)
{
	if (is_full(q))
		return;
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element dequeue(QueueType* q)
{
	if (is_empty(q))
		return;
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

int size(QueueType* q)
{
	return (q->rear - q->front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

int main()
{
	int num = 0;
	QueueType q;
	init_queue(&q);
	scanf("%d", &num);
	for (int i = 1;i <= num;i++)
	{
		enqueue(&q, i);
	}
	while (1)
	{
		if (size(&q) == 1)
		{
			printf("1");
			return 0;
		}
		dequeue(&q);
		if (size(&q) == 1)
			break;
		enqueue(&q, dequeue(&q));
	 }
	printf("%d", dequeue(&q));
	return 0;

}

마무리 : C++로 풀기 전 학교 공부 할겸 C로 풀었던 문제이다. 이 문제는 큐로 풀어도 되고 원형큐로 풀어도 된다. 이 소스에소는 원형큐로 풀었던 문제이고. 문제에 나와있는 것처럼 메인 함수에서 맨 위를 빼고 그 맨위를 맨 아래로 보내게 만들었다. 만약 C++로 풀었다면 눈에 띄게 줄어들 것이다.